(*s: semgrep/matching/Generic_vs_generic.ml *)
(*s: pad/r2c copyright *)
(* Yoann Padioleau
 *
 * Copyright (C) 2019-2021 r2c
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * version 2.1 as published by the Free Software Foundation, with the
 * special exception on linking described in file license.txt.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the file
 * license.txt for more details.
 *)
(*e: pad/r2c copyright *)
open Common

(* A is the pattern, and B the concrete source code. For now
 * we both use the same module but they may differ later
 * as the expressivity of the pattern language grows.
 *
 * subtle: use 'b' to report errors, because 'a' is the sgrep pattern and it
 * has no file information usually.
 *)
module A = AST_generic
module B = AST_generic
module MV = Metavariable
module AST = AST_generic
module Flag = Flag_semgrep
module Config = Config_semgrep_t
module H = AST_generic_helpers

(* optimisations *)
module CK = Caching.Cache_key
module Env = Metavariable_capture
module F = Bloom_filter
open Matching_generic

let logger = Logging.get_logger [ __MODULE__ ]

(*****************************************************************************)
(* Prelude *)
(*****************************************************************************)
(* AST generic vs AST generic code matcher.
 *
 * This module allows to match some AST elements against other AST elements in
 * a flexible way, providing a kind of grep but at a syntactical level.
 *
 * Most of the boilerplate code was generated by
 *    $ pfff/meta/gen_code -matcher_gen_all
 * using OCaml pad-style reflection (see commons/OCaml.ml) on
 * h_program-lang/AST_generic.ml.
 *
 * See pfff/matcher/fuzzy_vs_fuzzy.ml for another approach.
 *
 * There are four main features allowing a "pattern" to match some "code":
 *  - metavariables can match anything (see metavar: tag in this file)
 *  - '...' can match any sequence (see dots: tag)
 *  - simple constructs match complex constructs having more details
 *    (e.g., the absence of attribute in a pattern will still match functions
 *     having many attributes) (see less-is-ok: tag)
 *  - the underlying AST uses some normalization (!= is transformed in !(..=))
 *    to support certain code equivalences (see equivalence: tag)
 *  - we do not care about differences in spaces/indentations/comments.
 *    we work at the AST-level.
 *
 * alternatives:
 *  - would it be simpler to work on a simpler AST, like a Term language,
 *    or even a Node/Leaf? or Ast_fuzzy? the "less-is-ok" would be
 *    difficult with that approach, because you need to know that some
 *    parts of the AST are attributes/annotations that can be skipped.
 *    In the same way, code equivalences like name resolution on the AST
 *    would be more difficult with an untyped-general tree.
 *)

(*****************************************************************************)
(* Extra Helpers *)
(*****************************************************************************)

let env_add_matched_stmt rightmost_stmt (tin : tin) =
  [ extend_stmts_match_span rightmost_stmt tin ]

(*s: function [[Generic_vs_generic.m_string_xhp_text]] *)
(* equivalence: on different indentation
 * todo? work? was copy-pasted from XHP sgrep matcher
 *)
let m_string_xhp_text sa sb =
  if sa =$= sb || (sa =~ "^[\n ]+$" && sb =~ "^[\n ]+$") then return ()
  else fail ()

(*e: function [[Generic_vs_generic.m_string_xhp_text]] *)

(* less: could be made more general by taking is_dots function parameter *)
let has_ellipsis_and_filter_ellipsis xs =
  let has_ellipsis = ref false in
  let ys =
    xs
    |> Common.exclude (function
         | A.Ellipsis _ ->
             has_ellipsis := true;
             true
         | _ -> false)
  in
  (!has_ellipsis, ys)

let has_xml_ellipsis_and_filter_ellipsis xs =
  let has_ellipsis = ref false in
  let ys =
    xs
    |> Common.exclude (function
         | A.XmlEllipsis _ ->
             has_ellipsis := true;
             true
         | _ -> false)
  in
  (!has_ellipsis, ys)

let has_case_ellipsis_and_filter_ellipsis xs =
  let has_ellipsis = ref false in
  let ys =
    xs
    |> Common.exclude (function
         | A.CaseEllipsis _ ->
             has_ellipsis := true;
             true
         | _ -> false)
  in
  (!has_ellipsis, ys)

let rec obj_and_method_calls_of_expr = function
  | B.Call (B.DotAccess (e, tok, fld), args) ->
      let o, xs = obj_and_method_calls_of_expr e in
      (o, (fld, tok, args) :: xs)
  | o -> (o, [])

let rec expr_of_obj_and_method_calls (obj, xs) =
  match xs with
  | [] -> obj
  | (fld, tok, args) :: xs ->
      let e = expr_of_obj_and_method_calls (obj, xs) in
      B.Call (B.DotAccess (e, tok, fld), args)

let rec all_suffix_of_list xs =
  xs :: (match xs with [] -> [] | _x :: xs -> all_suffix_of_list xs)

let _ =
  Common2.example
    (all_suffix_of_list [ 1; 2; 3 ] = [ [ 1; 2; 3 ]; [ 2; 3 ]; [ 3 ]; [] ])

(*****************************************************************************)
(* Optimisations (caching, bloom filter) *)
(*****************************************************************************)

(* Getters and setters that were left abstract in the cache implementation. *)
let cache_access : tin Caching.Cache.access =
  {
    get_span_field = (fun tin -> tin.stmts_match_span);
    set_span_field = (fun tin x -> { tin with stmts_match_span = x });
    get_mv_field = (fun tin -> tin.mv);
    set_mv_field = (fun tin mv -> { tin with mv });
  }

let stmts_may_match pattern_stmts (stmts : AST_generic.stmt list) =
  if not !Flag.use_bloom_filter then F.Maybe
  else
    let pattern_list =
      Bloom_annotation.list_of_pattern_strings (Ss pattern_stmts)
    in
    let pat_in_stmt pat (stmt : AST_generic.stmt) =
      match stmt.s_bf with None -> F.Maybe | Some bf -> F.mem pat bf
    in
    let rec pattern_in_any_stmt pat stmts acc =
      match stmts with
      | [] -> acc
      | stmt :: rest -> (
          match acc with
          | F.No -> pattern_in_any_stmt pat rest (pat_in_stmt pat stmt)
          | F.Maybe -> acc )
    in
    let patterns_all_in_stmts acc x =
      match acc with
      | F.No -> Bloom_filter.No
      | Maybe -> pattern_in_any_stmt x stmts F.No
    in
    List.fold_left patterns_all_in_stmts F.Maybe pattern_list
  [@@profiling]

(*****************************************************************************)
(* Name *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_ident]] *)
(* coupling: modify also m_ident_and_id_info *)
let m_ident a b =
  match (a, b) with
  (*s: [[Generic_vs_generic.m_ident()]] metavariable case *)
  (* metavar: *)
  | (str, tok), b when MV.is_metavar_name str ->
      envf (str, tok) (MV.Id (b, None))
  (*e: [[Generic_vs_generic.m_ident()]] metavariable case *)
  (*s: [[Generic_vs_generic.m_ident()]] regexp case *)
  (* in some languages such as Javascript certain entities like
   * fields can use strings for identifiers (e.g., {"myfield": 1}),
   * which gives the opportunity to use regexp string for fields
   * (e.g., {"=~/.*field/": $X}).
   *)
  | (stra, _), (strb, _) when Pattern.is_regexp_string stra ->
      let re_match = Matching_generic.regexp_matcher_of_regexp_string stra in
      if re_match strb then return () else fail ()
  (*e: [[Generic_vs_generic.m_ident()]] regexp case *)
  (* general case *)
  | a, b -> (m_wrap m_string) a b

(*e: function [[Generic_vs_generic.m_ident]] *)

(*s: function [[Generic_vs_generic.m_dotted_name]] *)
let m_dotted_name a b =
  match (a, b) with
  (* TODO: [$X] should match any list *)
  | a, b -> (m_list m_ident) a b

(*e: function [[Generic_vs_generic.m_dotted_name]] *)

(*s: function [[Generic_vs_generic.make_dotted]] *)
(* This is for languages like Python where foo.arg.func is not parsed
 * as a qualified name but as a chain of DotAccess.
 *)
let make_dotted xs =
  match xs with
  | [] -> raise Impossible
  | x :: xs ->
      let base = B.N (B.Id (x, B.empty_id_info ())) in
      List.fold_left
        (fun acc e ->
          let tok = Parse_info.fake_info "." in
          B.DotAccess (acc, tok, B.EN (B.Id (e, B.empty_id_info ()))))
        base xs

(*e: function [[Generic_vs_generic.make_dotted]] *)

(* similar to m_list_prefix but binding $X to the whole list *)
let rec m_dotted_name_prefix_ok a b =
  match (a, b) with
  | [], [] -> return ()
  | [ (s, t) ], [ x ] when MV.is_metavar_name s -> envf (s, t) (MV.Id (x, None))
  | [ (s, t) ], _ :: _ when MV.is_metavar_name s ->
      (* TODO: should we bind it instead to a MV.N IdQualified?
       * but it is actually just the qualifier part; the last id
       * is not here (even though make_dottd will not care about that)
       *)
      envf (s, t) (MV.E (make_dotted b))
  | xa :: aas, xb :: bbs ->
      let* () = m_ident xa xb in
      m_dotted_name_prefix_ok aas bbs
  (* prefix is ok *)
  | [], _ -> return ()
  | _ :: _, _ -> fail ()

(*s: function [[Generic_vs_generic.m_module_name_prefix]] *)
(* less-is-ok: prefix matching is supported for imports, eg.:
 *  pattern: import foo.x should match: from foo.x.z.y
 *)
let m_module_name_prefix a b =
  match (a, b) with
  (* metavariable case *)
  | A.FileName ((a_str, _) as a1), B.FileName b1 when MV.is_metavar_name a_str
    ->
      (* Bind as a literal string expression so that pretty-printing works.
       * This also means that this metavar can match both literal strings and
       * filenames with the same string content. *)
      envf a1 (MV.E (B.L (B.String b1)))
  (* dots: '...' on string or regexp *)
  | A.FileName a, B.FileName b ->
      m_string_ellipsis_or_metavar_or_default
      (* TODO figure out what prefix support means here *)
        ~m_string_for_default:m_string_prefix a b
  | A.DottedName a1, B.DottedName b1 -> m_dotted_name_prefix_ok a1 b1
  | A.FileName _, _ | A.DottedName _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_module_name_prefix]] *)

(*s: function [[Generic_vs_generic.m_module_name]] *)
let m_module_name a b =
  match (a, b) with
  | A.FileName a1, B.FileName b1 -> (m_wrap m_string) a1 b1
  | A.DottedName a1, B.DottedName b1 -> m_dotted_name a1 b1
  | A.FileName _, _ | A.DottedName _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_module_name]] *)

(*s: function [[Generic_vs_generic.m_sid]] *)
let m_sid a b = if a =|= b then return () else fail ()

(*e: function [[Generic_vs_generic.m_sid]] *)

(*s: function [[Generic_vs_generic.m_resolved_name_kind]] *)
let m_resolved_name_kind a b =
  match (a, b) with
  | A.Local, B.Local -> return ()
  | A.EnclosedVar, B.EnclosedVar -> return ()
  | A.Param, B.Param -> return ()
  | A.Global, B.Global -> return ()
  | A.ImportedEntity a1, B.ImportedEntity b1 -> m_dotted_name a1 b1
  | A.ImportedModule a1, B.ImportedModule b1 -> m_module_name a1 b1
  | A.Macro, B.Macro -> return ()
  | A.EnumConstant, B.EnumConstant -> return ()
  | A.TypeName, B.TypeName -> return ()
  | A.Local, _
  | A.Param, _
  | A.Global, _
  | A.EnclosedVar, _
  | A.Macro, _
  | A.EnumConstant, _
  | A.TypeName, _
  | A.ImportedEntity _, _
  | A.ImportedModule _, _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_resolved_name_kind]] *)

(*s: function [[Generic_vs_generic._m_resolved_name]] *)
let _m_resolved_name (a1, a2) (b1, b2) =
  let* () = m_resolved_name_kind a1 b1 in
  m_sid a2 b2

(*e: function [[Generic_vs_generic._m_resolved_name]] *)

(* start of recursive need *)
(*s: function [[Generic_vs_generic.m_name]] *)
(* TODO: factorize metavariable and aliasing logic in m_expr, m_type, m_attr
 * here, and use a new MV.N instead of MV.Id
 *)
let rec m_name a b =
  match (a, b) with
  | A.Id (a1, a2), B.Id (b1, b2) -> m_ident a1 b1 >>= fun () -> m_id_info a2 b2
  | A.IdQualified (a1, a2), B.IdQualified (b1, b2) ->
      m_name_ a1 b1 >>= fun () -> m_id_info a2 b2
  | A.Id _, _ | A.IdQualified _, _ -> fail ()

and m_name_ a b =
  match (a, b) with
  | (a1, a2), (b1, b2) -> m_ident a1 b1 >>= fun () -> m_name_info a2 b2

(*e: function [[Generic_vs_generic.m_name]] *)

(*s: function [[Generic_vs_generic.m_name_info]] *)
and m_name_info a b =
  match (a, b) with
  | ( { A.name_qualifier = a1; name_typeargs = a2 },
      { B.name_qualifier = b1; name_typeargs = b2 } ) ->
      (m_option m_qualifier) a1 b1 >>= fun () ->
      (m_option m_type_arguments) a2 b2

(*e: function [[Generic_vs_generic.m_name_info]] *)
and m_qualifier a b =
  match (a, b) with
  | A.QDots a, B.QDots b -> m_dotted_name a b
  | A.QTop a, B.QTop b -> m_tok a b
  | A.QExpr (a1, a2), B.QExpr (b1, b2) -> m_expr a1 b1 >>= fun () -> m_tok a2 b2
  | A.QDots _, _ | A.QTop _, _ | A.QExpr _, _ -> fail ()

and m_type_option_with_hook idb taopt tbopt =
  match (taopt, tbopt) with
  | Some ta, Some tb -> m_type_ ta tb
  | Some ta, None -> (
      match !Hooks.get_type idb with
      | Some tb -> m_type_ ta tb
      | None -> fail () )
  (* less-is-ok:, like m_option_none_can_match_some *)
  | None, _ -> return ()

(*s: function [[Generic_vs_generic.m_ident_and_id_info_add_in_env_Expr]] *)
and m_ident_and_id_info (a1, a2) (b1, b2) =
  (* metavar: *)
  match (a1, b1) with
  | (str, tok), b when MV.is_metavar_name str ->
      (* a bit OCaml specific, cos only ml_to_generic tags id_type in pattern *)
      m_type_option_with_hook b1 !(a2.A.id_type) !(b2.B.id_type) >>= fun () ->
      m_id_info a2 b2 >>= fun () -> envf (str, tok) (MV.Id (b, Some b2))
  (* same code than for m_ident *)
  (*s: [[Generic_vs_generic.m_ident()]] regexp case *)
  (* in some languages such as Javascript certain entities like
   * fields can use strings for identifiers (e.g., {"myfield": 1}),
   * which gives the opportunity to use regexp string for fields
   * (e.g., {"=~/.*field/": $X}).
   *)
  | (stra, _), (strb, _) when Pattern.is_regexp_string stra ->
      let re_match = Matching_generic.regexp_matcher_of_regexp_string stra in
      if re_match strb then return () else fail ()
  (*e: [[Generic_vs_generic.m_ident()]] regexp case *)
  (* general case *)
  (* todo: we should check m_id_info, but anyway this function is currently
   * a nop *)
  | a, b -> (m_wrap m_string) a b

(*e: function [[Generic_vs_generic.m_ident_and_id_info_add_in_env_Expr]] *)
and m_ident_and_empty_id_info a1 b1 =
  let empty = AST.empty_id_info () in
  m_ident_and_id_info (a1, empty) (b1, empty)

(*s: function [[Generic_vs_generic.m_id_info]] *)
(* Currently m_id_info is a Nop because the Semgrep pattern usually
 * does not have correct name resolution (see the comment below).
 * However, we do use id_info in equal_ast() to check
 * whether two $X refers to the same code. In that case we are using
 * the id_resolved tag and sid!
 *)
and m_id_info a b =
  match (a, b) with
  | ( { A.id_resolved = _a1; id_type = _a2; id_constness = _a3 },
      { B.id_resolved = _b1; id_type = _b2; id_constness = _b3 } ) ->
      (* old: (m_ref m_resolved_name) a3 b3  >>= (fun () ->
       * but doing import flask in a source file means every reference
       * to flask.xxx will be tagged with a ImportedEntity, but
       * semgrep pattern will use flask.xxx directly, without the preceding
       * import, without this tag, which would prevent
       * matching. We need to correctly resolve names and always compare with
       * the resolved_name instead of the name used in the code
       * (which can be an alias)
       *
       * old: (m_ref (m_option m_type_)) a2 b2
       * the same is true for types! Now we sometimes propagate type annotations
       * in Naming_AST.ml, but we do that in the source file, not the pattern,
       * which would prevent a match.
       * More generally, id_info is something populated and used on the
       * generic AST of the source, not on the pattern, hence we should
       * not use it as a condition for matching here. Instead use
       * the information in the caller.
       *)
      return ()

(*e: function [[Generic_vs_generic.m_id_info]] *)

(*****************************************************************************)
(* Expression *)
(*****************************************************************************)

(* possibly go deeper when someone wants that a pattern like
 *   'bar();'
 * match also an expression statement like
 *   'x = bar();'.
 *
 * This is very hacky.
 *
 * alternatives:
 *  - force the user to use 'if(... <expr> ...)' (isaac, jmelton)
 *  - do as in coccinelle and use 'if(<... <expr> ...>)'
 *  - CURRENT: impicitely go deep without requiring an extra syntax
 *
 * todo? we could restrict ourselves to only a few forms? see SubAST_generic.ml
 *   - x = <expr>,
 *   - <call>(<exprs).
 *)
(* experimental! *)
(*s: function [[Generic_vs_generic.m_expr_deep]] *)
and m_expr_deep a b =
  if_config
    (fun x -> not x.go_deeper_expr)
    ~then_:(m_expr a b)
    ~else_:
      ( m_expr a b >!> fun () ->
        let subs = SubAST_generic.subexprs_of_expr b in
        (* less: could use a fold *)
        let rec aux xs =
          match xs with [] -> fail () | x :: xs -> m_expr_deep a x >||> aux xs
        in
        aux subs )

(*e: function [[Generic_vs_generic.m_expr_deep]] *)

(* coupling: if you add special sgrep hooks here, you should probably
 * also add them in m_pattern
 *)
(*s: function [[Generic_vs_generic.m_expr]] *)
and m_expr a b =
  match (a, b) with
  (* the order of the matches matters! take care! *)
  (*s: [[Generic_vs_generic.m_expr()]] disjunction case *)
  (* equivalence: user-defined equivalence! *)
  | A.DisjExpr (a1, a2), b -> m_expr a1 b >||> m_expr a2 b
  (*e: [[Generic_vs_generic.m_expr()]] disjunction case *)
  (*s: [[Generic_vs_generic.m_expr()]] resolving alias case *)
  (* equivalence: name resolving! *)
  | ( a,
      B.N
        (B.Id
          ( idb,
            {
              B.id_resolved =
                {
                  contents =
                    Some
                      ( ( B.ImportedEntity dotted
                        | B.ImportedModule (B.DottedName dotted) ),
                        _sid );
                };
              _;
            } )) ) ->
      (* We used to force to fully qualify entities in the pattern
       * (e.g., with org.foo(...)) but this is confusing for users.
       * We now allow an unqualified pattern like 'foo' to match resolved
       * entities like import org.foo; foo(), just like for attributes.
       *)
      m_expr a (B.N (B.Id (idb, B.empty_id_info ())))
      >||> (* try this time a match with the resolved entity *)
      m_expr a (make_dotted dotted)
  (* Put this before the next case to prevent overly eager dealiasing *)
  | A.N (A.IdQualified (a1, a2)), B.N (B.IdQualified (b1, b2)) ->
      m_name_ a1 b1 >>= fun () -> m_id_info a2 b2
  (* Matches pattern
   *   a.b.C.x
   * to code
   *   import a.b.C
   *   C.x
   *)
  | ( A.N
        (A.IdQualified
          ((alabel, { A.name_qualifier = Some (A.QDots names); _ }), _id_info)),
      b ) ->
      let full = names @ [ alabel ] in
      m_expr (make_dotted full) b
  (*e: [[Generic_vs_generic.m_expr()]] resolving alias case *)
  (*s: [[Generic_vs_generic.m_expr()]] metavariable case *)
  (*s: [[Generic_vs_generic.m_expr()]] forbidden metavariable case *)
  (* $X should not match an IdSpecial in a call context,
   * otherwise $X(...) would match a+b because this is transformed in a
   * Call(IdSpecial Plus, ...).
   * bugfix: note that we must forbid that only in a Call context; we want
   * $THIS to match IdSpecial (This) for example.
   *)
  | ( A.Call (A.N (A.Id ((str, _tok), _id_info)), _argsa),
      B.Call (B.IdSpecial _, _argsb) )
    when MV.is_metavar_name str ->
      fail ()
  (* metavar: *)
  (* Matching a generic Id metavariable to an IdSpecial will fail as it is missing the token
   * info; instead the Id should match Call(IdSpecial _, _)
   *)
  | A.N (A.Id ((str, _), _)), B.IdSpecial (B.ConcatString _, _)
  | A.N (A.Id ((str, _), _)), B.IdSpecial (B.Instanceof, _)
  | A.N (A.Id ((str, _), _)), B.IdSpecial (B.New, _)
    when MV.is_metavar_name str ->
      fail ()
  (*e: [[Generic_vs_generic.m_expr()]] forbidden metavariable case *)
  (* TODO: factorize in m_name? *)
  | A.N (A.Id ((str, tok), _id_info)), B.N (B.Id (idb, id_infob))
    when MV.is_metavar_name str ->
      envf (str, tok) (MV.Id (idb, Some id_infob))
  | A.N (A.Id ((str, tok), _id_info)), e2 when MV.is_metavar_name str ->
      envf (str, tok) (MV.E e2)
  (*e: [[Generic_vs_generic.m_expr()]] metavariable case *)
  (*s: [[Generic_vs_generic.m_expr()]] typed metavariable case *)
  (* metavar: typed! *)
  | A.TypedMetavar ((str, tok), _, t), e2 when MV.is_metavar_name str ->
      m_compatible_type (str, tok) t e2
  (*e: [[Generic_vs_generic.m_expr()]] typed metavariable case *)
  (*s: [[Generic_vs_generic.m_expr()]] ellipsis cases *)
  (* dots: should be patterned-match before in arguments, or statements,
   * but this is useful for keyword parameters, as in f(..., foo=..., ...)
   *)
  | A.Ellipsis _a1, _ -> return ()
  (*x: [[Generic_vs_generic.m_expr()]] ellipsis cases *)
  | A.DeepEllipsis (_, a1, _), a2 ->
      m_expr_deep a1 a2 (*e: [[Generic_vs_generic.m_expr()]] ellipsis cases *)
  (* must be before constant propagation case below *)
  | A.L a1, B.L b1 -> m_literal a1 b1
  (*s: [[Generic_vs_generic.m_expr()]] propagated constant case *)
  (* equivalence: constant propagation and evaluation!
   * TODO: too late, must do that before 'metavar:' so that
   * const a = "foo"; ... a == "foo" would be catched by $X == $X.
   *)
  | A.L a1, b1 ->
      if_config
        (fun x -> x.Config.constant_propagation)
        ~then_:
          ( match
              Normalize_generic.constant_propagation_and_evaluate_literal b1
            with
          | Some b1 -> m_literal_constness a1 b1
          | None -> fail () )
        ~else_:(fail ())
  (*e: [[Generic_vs_generic.m_expr()]] propagated constant case *)
  (*s: [[Generic_vs_generic.m_expr()]] sequencable container cases *)
  | A.Container (A.Array, a2), B.Container (B.Array, b2) ->
      (m_bracket m_container_ordered_elements) a2 b2
  | A.Container (A.List, a2), B.Container (B.List, b2) ->
      (m_bracket m_container_ordered_elements) a2 b2
  | A.Tuple a1, B.Tuple b1 -> (m_container_ordered_elements |> m_bracket) a1 b1
  (*e: [[Generic_vs_generic.m_expr()]] sequencable container cases *)
  | ( A.Container (((A.Set | A.Dict) as a1), (_, a2, _)),
      B.Container (((B.Set | B.Dict) as b1), (_, b2, _)) ) ->
      m_container_set_or_dict_unordered_elements (a1, a2) (b1, b2)
  (*s: [[Generic_vs_generic.m_expr()]] interpolated strings case *)
  (* dots '...' for string literal:
   * Interpolated strings are transformed into Call(Special(Concat, ...),
   * hence we want Python patterns like f"...{$X}...", which are expanded to
   * Call(Special(Concat, [L"..."; Id "$X"; L"..."])) to
   * match concrete code like f"foo{a}" such that "..." is seemingly
   * matching 0 or more literal expressions.
   * bugfix: note that we want to do that only when inside
   * Call(Special(Concat(...))), hence the special m_arguments_concat below,
   * otherwise regular call patterns like foo("...") would match code like
   * foo().
   *)
  | ( A.Call (A.IdSpecial (A.ConcatString akind, _a1), a2),
      B.Call (B.IdSpecial (B.ConcatString bkind, _b1), b2) ) ->
      m_concat_string_kind akind bkind >>= fun () ->
      m_bracket m_arguments_concat a2 b2
  (*e: [[Generic_vs_generic.m_expr()]] interpolated strings case *)
  (* The pattern '$X = 1 + 2 + ...' is parsed as '$X = (1 + 2) + ...', but
   * if the concrete code is 'foo = 1 + 2 + 3 + 4', this will naively not
   * match because (1+2)+... will be matched against ((1+2)+3)+4 and fails.
   * The ellipsis operator with binary operators should be more flexible
   * and allows any number of additional arguments, which when translated
   * in Call() means we need to go deeper.
   *)
  | ( A.Call
        ( A.IdSpecial (A.Op aop, _toka),
          (_, [ A.Arg a1; A.Arg (A.Ellipsis _tdots) ], _) ),
      B.Call (B.IdSpecial (B.Op bop, _tokb), (_, [ B.Arg b1; B.Arg _b2 ], _)) )
  (* This applies to any binary operation! Associative operators (declared
   * in AST_generic_helpers.is_associative_operator) are better handled by
   * m_call_op below. *)
    when (not (H.is_associative_operator aop)) || aop <> bop ->
      m_arithmetic_operator aop bop >>= fun () ->
      m_expr a1 b1 >!> fun () ->
      (* try again deeper on b1 *)
      m_expr a b1
  | ( A.Call (A.IdSpecial (A.Op aop, toka), aargs),
      B.Call (B.IdSpecial (B.Op bop, tokb), bargs) ) ->
      m_call_op aop toka aargs bop tokb bargs
  (* boilerplate *)
  (* TODO: via m_name! and miss IdQualfied vs IdQualified otherwise *)
  | A.N (A.Id (a1, a2)), B.N (B.Id (b1, b2)) ->
      m_ident a1 b1 >>= fun () -> m_id_info a2 b2
  | A.Call (a1, a2), B.Call (b1, b2) ->
      m_expr a1 b1 >>= fun () -> m_arguments a2 b2
  | A.Assign (a1, at, a2), B.Assign (b1, bt, b2) -> (
      m_expr a1 b1
      >>= (fun () -> m_tok at bt >>= fun () -> m_expr a2 b2)
      (* If the code has tuples as b1 and b2 and the lengths of
       * the tuples are equal, create a tuple of (variable, value)
       * pairs and try to match the pattern with each entry in the tuple.
       * This should enable multiple assignments if the number of
       * variables and values are equal. *)
      >||>
      match (b1, b2) with
      | B.Tuple (_, vars, _), B.Tuple (_, vals, _)
        when List.length vars = List.length vals ->
          let create_assigns expr1 expr2 = B.Assign (expr1, bt, expr2) in
          let mult_assigns = List.map2 create_assigns vars vals in
          let rec aux xs =
            match xs with [] -> fail () | x :: xs -> m_expr a x >||> aux xs
          in
          aux mult_assigns
      | _, _ -> fail () )
  | A.DotAccess (a1, at, a2), B.DotAccess (b1, bt, b2) ->
      m_expr a1 b1 >>= fun () ->
      m_tok at bt >>= fun () -> m_name_or_dynamic a2 b2
  (* <a1> ... vs o.m1().m2().m3().
   * Remember than o.m1().m2().m3() is parsed as (((o.m1()).m2()).m3())
   *)
  | A.DotAccessEllipsis (a1, _a2), (B.DotAccess _ | B.Call (B.DotAccess _, _))
    ->
      (* => o, [m3();m2();m1() *)
      let obj, ys = obj_and_method_calls_of_expr b in
      (* the method chain ellipsis can match 0 or more of those method calls *)
      let candidates = all_suffix_of_list ys in
      let rec aux xxs =
        match xxs with
        | [] -> fail ()
        | xs :: xxs ->
            let b = expr_of_obj_and_method_calls (obj, xs) in
            m_expr a1 b >||> aux xxs
      in
      aux candidates
  | A.ArrayAccess (a1, a2), B.ArrayAccess (b1, b2) ->
      m_expr a1 b1 >>= fun () -> m_bracket m_expr a2 b2
  (*s: [[Generic_vs_generic.m_expr()]] boilerplate cases *)
  | A.Record a1, B.Record b1 -> (m_bracket m_fields) a1 b1
  | A.Constructor (a1, a2), B.Constructor (b1, b2) ->
      m_dotted_name a1 b1 >>= fun () -> (m_list m_expr) a2 b2
  | A.Lambda a1, B.Lambda b1 ->
      m_function_definition a1 b1 >>= fun () -> return ()
  | A.AnonClass a1, B.AnonClass b1 -> m_class_definition a1 b1
  | A.IdSpecial a1, B.IdSpecial b1 -> m_wrap m_special a1 b1
  (* This is mainly for Go which generates an AssignOp (Eq)
   * for the x := a short variable declaration.
   * TODO: this should be a configurable equivalence: $X = $Y ==> $X := $Y.
   * Some people want it, some people may not want it.
   * At least we dont do the opposite (AssignOp matching Assign) so
   * using := in a pattern will not match code using just =
   * (but pattern using = will match both code using = or :=).
   *)
  | A.Assign (a1, a2, a3), B.AssignOp (b1, (B.Eq, b2), b3) ->
      m_expr (A.Assign (a1, a2, a3)) (B.Assign (b1, b2, b3))
  | A.AssignOp (a1, a2, a3), B.AssignOp (b1, b2, b3) ->
      m_expr a1 b1 >>= fun () ->
      m_wrap m_arithmetic_operator a2 b2 >>= fun () -> m_expr a3 b3
  | A.Xml a1, B.Xml b1 -> m_xml a1 b1
  | A.LetPattern (a1, a2), B.LetPattern (b1, b2) ->
      m_pattern a1 b1 >>= fun () -> m_expr a2 b2
  | A.SliceAccess (a1, a2), B.SliceAccess (b1, b2) ->
      let f = m_option m_expr in
      m_expr a1 b1 >>= fun () -> m_bracket (m_tuple3 f f f) a2 b2
  | A.Conditional (a1, a2, a3), B.Conditional (b1, b2, b3) ->
      m_expr a1 b1 >>= fun () ->
      m_expr a2 b2 >>= fun () -> m_expr a3 b3
  | A.MatchPattern (a1, a2), B.MatchPattern (b1, b2) ->
      m_expr a1 b1 >>= fun () -> (m_list m_action) a2 b2
  | A.Yield (a0, a1, a2), B.Yield (b0, b1, b2) ->
      m_tok a0 b0 >>= fun () ->
      m_option m_expr a1 b1 >>= fun () -> m_bool a2 b2
  | A.Await (a0, a1), B.Await (b0, b1) -> m_tok a0 b0 >>= fun () -> m_expr a1 b1
  | A.Cast (a1, a2), B.Cast (b1, b2) -> m_type_ a1 b1 >>= fun () -> m_expr a2 b2
  | A.Seq a1, B.Seq b1 -> (m_list m_expr) a1 b1
  | A.Ref (a0, a1), B.Ref (b0, b1) -> m_tok a0 b0 >>= fun () -> m_expr a1 b1
  | A.DeRef (a0, a1), B.DeRef (b0, b1) -> m_tok a0 b0 >>= fun () -> m_expr a1 b1
  | A.OtherExpr (a1, a2), B.OtherExpr (b1, b2) ->
      m_other_expr_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.Container _, _
  | A.Tuple _, _
  | A.Record _, _
  | A.Constructor _, _
  | A.Lambda _, _
  | A.AnonClass _, _
  | A.N _, _
  | A.IdSpecial _, _
  | A.Call _, _
  | A.Xml _, _
  | A.Assign _, _
  | A.AssignOp _, _
  | A.LetPattern _, _
  | A.DotAccess _, _
  | A.ArrayAccess _, _
  | A.SliceAccess _, _
  | A.Conditional _, _
  | A.MatchPattern _, _
  | A.Yield _, _
  | A.Await _, _
  | A.Cast _, _
  | A.Seq _, _
  | A.Ref _, _
  | A.DeRef _, _
  | A.OtherExpr _, _
  | A.TypedMetavar _, _
  | A.DotAccessEllipsis _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_expr()]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_expr]] *)

(*s: function [[Generic_vs_generic.m_field_ident]] *)
and m_name_or_dynamic a b =
  match (a, b) with
  (* TODO: factorize in m_name *)
  | A.EN (A.Id ((str, tok), a2)), B.EN (B.Id (idb, b2))
    when MV.is_metavar_name str ->
      (* a bit OCaml specific, cos only ml_to_generic tags id_type in pattern *)
      let* () = m_type_option_with_hook idb !(a2.A.id_type) !(b2.B.id_type) in
      let* () = m_id_info a2 b2 in
      envf (str, tok) (MV.Id (idb, Some b2))
  | A.EN (A.Id ((str, tok), _idinfoa)), b when MV.is_metavar_name str ->
      let e = H.name_or_dynamic_to_expr b None in
      envf (str, tok) (MV.E e)
  | A.EN (A.Id (a, idinfoa)), B.EN (B.Id (b, idinfob)) ->
      m_ident_and_id_info (a, idinfoa) (b, idinfob)
  (* boilerplate *)
  (*s: [[Generic_vs_generic.m_field_ident()]] boilerplate cases *)
  | A.EN a, B.EN b -> m_name a b
  | A.EDynamic a, B.EDynamic b -> m_expr a b
  | A.EN _, _ | A.EDynamic _, _ -> fail ()

(*e: [[Generic_vs_generic.m_field_ident()]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_field_ident]] *)

(*s: function [[Generic_vs_generic.m_label_ident]] *)
and m_label_ident a b =
  match (a, b) with
  | A.LNone, B.LNone -> return ()
  | A.LId a, B.LId b -> m_label a b
  | A.LInt a, B.LInt b -> m_wrap m_int a b
  | A.LDynamic a, B.LDynamic b -> m_expr a b
  | A.LNone, _ | A.LId _, _ | A.LInt _, _ | A.LDynamic _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_label_ident]] *)

(*s: function [[Generic_vs_generic.m_literal]] *)
and m_literal a b =
  match (a, b) with
  (*s: [[Generic_vs_generic.m_literal()]] ellipsis case *)
  (* dots: metavar: '...' and metavars on string/regexps/atoms *)
  | A.String a, B.String b -> m_string_ellipsis_or_metavar_or_default a b
  | A.Atom (_, a), B.Atom (_, b) -> m_ellipsis_or_metavar_or_string a b
  | A.Regexp (a1, a2), B.Regexp (b1, b2) -> (
      let* () = m_bracket m_ellipsis_or_metavar_or_string a1 b1 in
      match (a2, b2) with
      (* less_is_ok: *)
      | None, _ -> return ()
      | Some a, Some b -> m_ellipsis_or_metavar_or_string a b
      | Some _, None -> fail () )
  (*x: [[Generic_vs_generic.m_literal()]] ellipsis case *)
  (*e: [[Generic_vs_generic.m_literal()]] ellipsis case *)
  (*s: [[Generic_vs_generic.m_literal()]] regexp case *)
  (*e: [[Generic_vs_generic.m_literal()]] regexp case *)
  (* boilerplate *)
  | A.Unit a1, B.Unit b1 -> m_tok a1 b1
  | A.Bool a1, B.Bool b1 -> (m_wrap m_bool) a1 b1
  | A.Int a1, B.Int b1 -> m_wrap_m_int_opt a1 b1
  | A.Float a1, B.Float b1 -> m_wrap_m_float_opt a1 b1
  | A.Imag a1, B.Imag b1 -> (m_wrap m_string) a1 b1
  | A.Ratio a1, B.Ratio b1 -> (m_wrap m_string) a1 b1
  | A.Char a1, B.Char b1 -> (m_wrap m_string) a1 b1
  | A.Null a1, B.Null b1 -> m_tok a1 b1
  | A.Undefined a1, B.Undefined b1 -> m_tok a1 b1
  | A.Unit _, _
  | A.Bool _, _
  | A.Int _, _
  | A.Float _, _
  | A.Char _, _
  | A.String _, _
  | A.Regexp _, _
  | A.Null _, _
  | A.Undefined _, _
  | A.Imag _, _
  | A.Ratio _, _
  | A.Atom _, _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_literal]] *)
and m_wrap_m_int_opt (a1, a2) (b1, b2) =
  match (a1, b1) with
  (* iso: semantic equivalence of value! 0x8 can match 8 *)
  | Some i1, Some i2 -> if i1 =|= i2 then return () else fail ()
  (* if the integers (or floats) were too large or were using
   * a syntax OCaml int_of_string could not parse,
   * we default to a string comparison *)
  | _ ->
      let a1 = Parse_info.str_of_info a2 in
      (* bugfix: not that with constant propagation, some integers don't have
       * a real token associated with them, so b2 may be a FakeTok, but
       * Parse_info.str_of_info does not raise an exn anymore on a FakeTok
       *)
      let b1 = Parse_info.str_of_info b2 in
      m_wrap m_string (a1, a2) (b1, b2)

and m_wrap_m_float_opt (a1, a2) (b1, b2) =
  match (a1, b1) with
  (* iso: semantic equivalence of value! 0x8 can match 8 *)
  | Some i1, Some i2 when i1 = i2 -> return ()
  | _ ->
      let a1 = Parse_info.str_of_info a2 in
      let b1 = Parse_info.str_of_info b2 in
      m_wrap m_string (a1, a2) (b1, b2)

and m_literal_constness a b =
  match b with
  | B.Lit b1 -> m_literal a b1
  | B.Cst B.Cstr -> (
      match a with A.String ("...", _) -> return () | ___else___ -> fail () )
  | B.Cst _ | B.NotCst -> fail ()

(*s: function [[Generic_vs_generic.m_action]] *)
and m_action a b =
  match (a, b) with
  | (a1, a2), (b1, b2) -> m_pattern a1 b1 >>= fun () -> m_expr a2 b2

(*e: function [[Generic_vs_generic.m_action]] *)

(*s: function [[Generic_vs_generic.m_arithmetic_operator]] *)
and m_arithmetic_operator a b =
  match (a, b) with _ when a =*= b -> return () | _ -> fail ()

(*e: function [[Generic_vs_generic.m_arithmetic_operator]] *)

(*s: function [[Generic_vs_generic.m_special]] *)
and m_special a b =
  match (a, b) with
  | A.This, B.This -> return ()
  | A.Super, B.Super -> return ()
  | A.Self, B.Self -> return ()
  | A.Parent, B.Parent -> return ()
  | A.Eval, B.Eval -> return ()
  | A.Typeof, B.Typeof -> return ()
  | A.Instanceof, B.Instanceof -> return ()
  | A.Sizeof, B.Sizeof -> return ()
  | A.New, B.New -> return ()
  | A.Defined, B.Defined -> return ()
  | A.ConcatString a, B.ConcatString b -> m_concat_string_kind a b
  | A.InterpolatedElement, B.InterpolatedElement -> return ()
  | A.Spread, B.Spread -> return ()
  | A.HashSplat, B.HashSplat -> return ()
  | A.ForOf, B.ForOf -> return ()
  | A.Op a1, B.Op b1 -> m_arithmetic_operator a1 b1
  | A.EncodedString a1, B.EncodedString b1 -> m_string a1 b1
  | A.IncrDecr (a1, a2), B.IncrDecr (b1, b2) ->
      m_eq a1 b1 >>= fun () -> m_eq a2 b2
  | A.NextArrayIndex, B.NextArrayIndex -> return ()
  | A.This, _
  | A.Super, _
  | A.Self, _
  | A.Parent, _
  | A.Eval, _
  | A.Typeof, _
  | A.Instanceof, _
  | A.Sizeof, _
  | A.New, _
  | A.ConcatString _, _
  | A.Spread, _
  | A.Op _, _
  | A.IncrDecr _, _
  | A.EncodedString _, _
  | A.HashSplat, _
  | A.Defined, _
  | A.ForOf, _
  | A.NextArrayIndex, _
  | InterpolatedElement, _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_special]] *)
and m_concat_string_kind a b =
  match (a, b) with
  (* fstring pattern should match only fstring *)
  | A.FString, B.FString -> return ()
  | A.FString, _ -> fail ()
  (* same for tagged template literals *)
  | A.TaggedTemplateLiteral, B.TaggedTemplateLiteral -> return ()
  | A.TaggedTemplateLiteral, _ | _, B.TaggedTemplateLiteral -> fail ()
  (* less-is-more: *)
  | _ -> return ()

and m_container_set_or_dict_unordered_elements (a1, a2) (b1, b2) =
  match ((a1, a2), (b1, b2)) with
  (* those rules should be applied only for python? *)
  | ((A.Dict | A.Set), []), ((A.Dict | A.Set), []) -> return ()
  | ((A.Dict | A.Set), [ A.Ellipsis _ ]), ((A.Dict | A.Set), _) -> return ()
  | (A.Set, a2), (B.Set, b2) ->
      let has_ellipsis, a2 = has_ellipsis_and_filter_ellipsis a2 in
      m_list_in_any_order ~less_is_ok:has_ellipsis m_expr a2 b2
  | (A.Dict, a2), (B.Dict, b2) ->
      let has_ellipsis, a2 = has_ellipsis_and_filter_ellipsis a2 in
      m_list_in_any_order ~less_is_ok:has_ellipsis m_expr a2 b2
  | _, _ ->
      (* less: could return fail () *)
      m_container_operator a1 b1 >>= fun () -> m_list m_expr a2 b2

(*s: function [[Generic_vs_generic.m_container_operator]] *)
(* coupling: if you add a constructor in AST_generic.container,
 * you probrably need to update m_container_set_or_dict_unordered_elements
 * and m_expr to handle this new kind of container.
 *)
and m_container_operator a b =
  match (a, b) with
  (* boilerplate *)
  | A.Array, B.Array -> return ()
  | A.List, B.List -> return ()
  | A.Set, B.Set -> return ()
  | A.Dict, B.Dict -> return ()
  | A.Array, _ | A.List, _ | A.Set, _ | A.Dict, _ -> fail ()

(*e: function [[Generic_vs_generic.m_container_operator]] *)

(*s: function [[Generic_vs_generic.m_container_ordered_elements]] *)
and m_container_ordered_elements a b =
  m_list_with_dots m_expr
    (function A.Ellipsis _ -> true | _ -> false)
    false (* empty list can not match non-empty list *) a b

(*e: function [[Generic_vs_generic.m_container_ordered_elements]] *)

(*s: function [[Generic_vs_generic.m_other_expr_operator]] *)
and m_other_expr_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_expr_operator]] *)
and m_compatible_type typed_mvar t e =
  match (t, e) with
  (* for Python literal checking *)
  | ( A.OtherType (A.OT_Expr, [ A.E (A.N (A.Id (("int", _tok), _idinfo))) ]),
      B.L (B.Int _) ) ->
      envf typed_mvar (MV.E e)
  | ( A.OtherType (A.OT_Expr, [ A.E (A.N (A.Id (("float", _tok), _idinfo))) ]),
      B.L (B.Float _) ) ->
      envf typed_mvar (MV.E e)
  | ( A.OtherType (A.OT_Expr, [ A.E (A.N (A.Id (("str", _tok), _idinfo))) ]),
      B.L (B.String _) ) ->
      envf typed_mvar (MV.E e)
  (* for java literals *)
  | A.TyBuiltin ("int", _), B.L (B.Int _) -> envf typed_mvar (MV.E e)
  | A.TyBuiltin ("float", _), B.L (B.Float _) -> envf typed_mvar (MV.E e)
  | A.TyN (A.Id (("String", _), _)), B.L (B.String _) ->
      envf typed_mvar (MV.E e)
  (* for C specific literals *)
  | A.TyPointer (_, TyBuiltin ("char", _)), B.L (B.String _) ->
      envf typed_mvar (MV.E e)
  | A.TyPointer (_, _), B.L (B.Null _) -> envf typed_mvar (MV.E e)
  (* for go literals *)
  | A.TyN (Id (("int", _), _)), B.L (B.Int _) -> envf typed_mvar (MV.E e)
  | A.TyN (Id (("float", _), _)), B.L (B.Float _) -> envf typed_mvar (MV.E e)
  | A.TyN (Id (("string", _), _)), B.L (B.String _) -> envf typed_mvar (MV.E e)
  (* for C strings to match metavariable pointer types *)
  | A.TyPointer (t1, A.TyN (A.Id ((_, tok), _id_info))), B.L (B.String _) ->
      m_type_ t (A.TyPointer (t1, TyBuiltin ("char", tok))) >>= fun () ->
      envf typed_mvar (MV.E e)
  (* for matching ids *)
  | ta, B.N (B.Id (idb, ({ B.id_type = tb; _ } as id_infob))) ->
      (* NOTE: Name values must be represented with MV.Id! *)
      m_type_option_with_hook idb (Some ta) !tb >>= fun () ->
      envf typed_mvar (MV.Id (idb, Some id_infob))
  | ( ta,
      ( B.N (B.IdQualified ((idb, _), { B.id_type = tb; _ }))
      | B.DotAccess
          (IdSpecial (This, _), _, EN (Id (idb, { B.id_type = tb; _ }))) ) ) ->
      m_type_option_with_hook idb (Some ta) !tb >>= fun () ->
      envf typed_mvar (MV.E e)
  | _ -> fail ()

(*---------------------------------------------------------------------------*)
(* XML *)
(*---------------------------------------------------------------------------*)

(*s: function [[Generic_vs_generic.m_xml]] *)
and m_xml a b =
  match (a, b) with
  | ( { A.xml_kind = a1; xml_attrs = a2; xml_body = a3 },
      { B.xml_kind = b1; xml_attrs = b2; xml_body = b3 } ) ->
      m_xml_kind a1 b1 >>= fun () ->
      m_attrs a2 b2 >>= fun () -> m_bodies a3 b3

(*e: function [[Generic_vs_generic.m_xml]] *)
and m_xml_kind a b =
  match (a, b) with
  (* iso: allow a Classic to match a Singleton, and vice versa *)
  | A.XmlClassic (a0, a1, a2, _), B.XmlSingleton (b0, b1, b2)
  | A.XmlSingleton (a0, a1, a2), B.XmlClassic (b0, b1, b2, _) ->
      let* () = m_tok a0 b0 in
      let* () = m_ident a1 b1 in
      let* () = m_tok a2 b2 in
      return ()
  | A.XmlClassic (a0, a1, a2, a3), B.XmlClassic (b0, b1, b2, b3) ->
      let* () = m_tok a0 b0 in
      let* () = m_ident a1 b1 in
      let* () = m_tok a2 b2 in
      let* () = m_tok a3 b3 in
      return ()
  | A.XmlSingleton (a0, a1, a2), B.XmlSingleton (b0, b1, b2) ->
      let* () = m_tok a0 b0 in
      let* () = m_ident a1 b1 in
      let* () = m_tok a2 b2 in
      return ()
  | A.XmlFragment (a1, a2), B.XmlFragment (b1, b2) ->
      let* () = m_tok a1 b1 in
      let* () = m_tok a2 b2 in
      return ()
  | A.XmlClassic _, _ | A.XmlSingleton _, _ | A.XmlFragment _, _ -> fail ()

(*s: function [[Generic_vs_generic.m_attrs]] *)
and m_attrs a b =
  let _has_ellipsis, a = has_xml_ellipsis_and_filter_ellipsis a in
  (* always implicit ... *)
  m_list_in_any_order ~less_is_ok:true m_xml_attr a b

(*e: function [[Generic_vs_generic.m_attrs]] *)

(*s: function [[Generic_vs_generic.m_bodies]] *)
and m_bodies a b = m_list__m_body a b

(*e: function [[Generic_vs_generic.m_bodies]] *)

(*s: function [[Generic_vs_generic.m_list__m_body]] *)
and m_list__m_body a b =
  match a with
  (* less-is-ok: it's ok to have an empty body in the pattern *)
  | [] -> return ()
  | _ -> m_list m_body a b

(*e: function [[Generic_vs_generic.m_list__m_body]] *)

(*s: function [[Generic_vs_generic.m_xml_attr]] *)
and m_xml_attr a b =
  match (a, b) with
  | A.XmlAttr (a1, at, a2), B.XmlAttr (b1, bt, b2) ->
      let* () = m_ident a1 b1 in
      let* () = m_tok at bt in
      m_xml_attr_value a2 b2
  | A.XmlAttrExpr a1, B.XmlAttrExpr b1 -> m_bracket m_expr a1 b1
  | A.XmlEllipsis a1, B.XmlEllipsis b1 -> m_tok a1 b1
  | A.XmlAttr _, _ | A.XmlAttrExpr _, _ | A.XmlEllipsis _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_xml_attr]] *)

(*s: function [[Generic_vs_generic.m_xml_attr_value]] *)
and m_xml_attr_value a b =
  (* less: deep? *)
  m_expr a b

(*e: function [[Generic_vs_generic.m_xml_attr_value]] *)

(*s: function [[Generic_vs_generic.m_body]] *)
and m_body a b =
  match (a, b) with
  | A.XmlText a1, B.XmlText b1 ->
      m_string_ellipsis_or_metavar_or_default
        ~m_string_for_default:m_string_xhp_text a1 b1
  (* boilerplate *)
  (*s: [[Generic_vs_generic.m_body]] boilerplate cases *)
  | A.XmlExpr a1, B.XmlExpr b1 ->
      (* less: could allow ... to match also a None *)
      m_bracket (m_option m_expr) a1 b1
  | A.XmlXml a1, B.XmlXml b1 -> m_xml a1 b1
  | A.XmlText _, _ | A.XmlExpr _, _ | A.XmlXml _, _ -> fail ()

(*e: [[Generic_vs_generic.m_body]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_body]] *)

(*---------------------------------------------------------------------------*)
(* Arguments list iso *)
(*---------------------------------------------------------------------------*)

(*s: function [[Generic_vs_generic.m_arguments]] *)
and m_arguments a b =
  match (a, b) with a, b -> m_bracket m_list__m_argument a b

(*e: function [[Generic_vs_generic.m_arguments]] *)

(* less: factorize in m_list_and_dots? but also has unordered for kwd args *)
(*s: function [[Generic_vs_generic.m_list__m_argument]] *)
and m_list__m_argument (xsa : A.argument list) (xsb : A.argument list) =
  match (xsa, xsb) with
  | [], [] -> return ()
  (*s: [[Generic_vs_generic.m_list__m_argument()]] ellipsis cases *)
  (* dots: ..., can also match no argument *)
  | [ A.Arg (A.Ellipsis _i) ], [] -> return ()
  (* dots: metavars: $...ARGS *)
  | A.Arg (A.N (A.Id ((s, tok), _idinfo))) :: xsa, xsb
    when MV.is_metavar_ellipsis s ->
      (* can match 0 or more arguments (just like ...) *)
      let candidates = inits_and_rest_of_list_empty_ok xsb in
      let rec aux xs =
        match xs with
        | [] -> fail ()
        | (inits, rest) :: xs ->
            envf (s, tok) (MV.Args inits)
            >>= (fun () -> m_list__m_argument xsa rest)
            >||> aux xs
      in
      aux candidates
  | A.Arg (A.Ellipsis i) :: xsa, xb :: xsb ->
      (* can match nothing *)
      m_list__m_argument xsa (xb :: xsb)
      >||> (* can match more *)
      m_list__m_argument (A.Arg (A.Ellipsis i) :: xsa) xsb
  (*e: [[Generic_vs_generic.m_list__m_argument()]] ellipsis cases *)
  (*s: [[Generic_vs_generic.m_list__m_argument()]] [[ArgKwd]] pattern case *)
  (* unordered kwd argument matching *)
  | (A.ArgKwd (((s, _tok) as ida), ea) as a) :: xsa, xsb -> (
      if MV.is_metavar_name s then
        (*s: [[Generic_vs_generic.m_list__m_argument()]] if metavar keyword argument *)
        let candidates = all_elem_and_rest_of_list xsb in
        (* less: could use a fold *)
        let rec aux xs =
          match xs with
          | [] -> fail ()
          | (b, xsb) :: xs ->
              m_argument a b
              >>= (fun () -> m_list__m_argument xsa (lazy_rest_of_list xsb))
              >||> aux xs
        in
        aux candidates
        (*e: [[Generic_vs_generic.m_list__m_argument()]] if metavar keyword argument *)
      else
        try
          let before, there, after =
            xsb
            |> Common2.split_when (function
                 | A.ArgKwd ((s2, _), _) when s =$= s2 -> true
                 | _ -> false)
          in
          match there with
          | A.ArgKwd (idb, eb) ->
              m_ident ida idb >>= fun () ->
              m_expr ea eb >>= fun () -> m_list__m_argument xsa (before @ after)
          | _ -> raise Impossible
        with Not_found -> fail () )
  (*e: [[Generic_vs_generic.m_list__m_argument()]] [[ArgKwd]] pattern case *)
  (* the general case *)
  | xa :: aas, xb :: bbs ->
      m_argument xa xb >>= fun () -> m_list__m_argument aas bbs
  | [], _ | _ :: _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_list__m_argument]] *)

(* special case m_arguments when inside a Call(Special(Concat,_), ...)
 * less: factorize with m_list_with_dots? hard because of the special
 * call to Normalize_generic below.
 *)
(*s: function [[Generic_vs_generic.m_arguments_concat]] *)
and m_arguments_concat a b =
  match (a, b) with
  | [], [] -> return ()
  (*s: [[Generic_vs_generic.m_arguments_concat()]] ellipsis cases *)
  (* dots '...' for string literal, can match any number of arguments *)
  | [ A.Arg (A.L (A.String ("...", _))) ], _xsb -> return ()
  (* specific case: f"...{$X}..." will properly extract $X from f"foo {bar} baz" *)
  | A.Arg (A.L (A.String ("...", a))) :: xsa, B.Arg bexpr :: xsb ->
      (* can match nothing *)
      m_arguments_concat xsa (B.Arg bexpr :: xsb)
      >||> (* can match more *)
      m_arguments_concat (A.Arg (A.L (A.String ("...", a))) :: xsa) xsb
  (*e: [[Generic_vs_generic.m_arguments_concat()]] ellipsis cases *)
  (* the general case *)
  | xa :: aas, xb :: bbs -> (
      (* exception: for concat strings, don't have ellipsis match   *)
      (* string literals since string literals are implicitly not   *)
      (* interpolated, and ellipsis implicitly is                   *)
      match (xa, xb) with
      | A.Arg (A.Ellipsis _), A.Arg (A.L (A.String _)) -> fail ()
      | _ -> m_argument xa xb >>= fun () -> m_arguments_concat aas bbs )
  | [], _ | _ :: _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_arguments_concat]] *)

(*s: function [[Generic_vs_generic.m_argument]] *)
and m_argument a b =
  match (a, b) with
  (* TODO: iso on keyword argument, keyword is optional in pattern *)

  (* boilerplate *)
  | A.Arg a1, B.Arg b1 -> m_expr a1 b1
  (*s: [[Generic_vs_generic.m_argument()]] boilerplate cases *)
  | A.ArgType a1, B.ArgType b1 -> m_type_ a1 b1
  | A.ArgKwd (a1, a2), B.ArgKwd (b1, b2) ->
      m_ident a1 b1 >>= fun () -> m_expr a2 b2
  | A.ArgOther (a1, a2), B.ArgOther (b1, b2) ->
      m_other_argument_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.Arg _, _ | A.ArgKwd _, _ | A.ArgType _, _ | A.ArgOther _, _ -> fail ()

(*e: [[Generic_vs_generic.m_argument()]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_argument]] *)

(*s: function [[Generic_vs_generic.m_other_argument_operator]] *)
and m_other_argument_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_argument_operator]] *)

(*---------------------------------------------------------------------------*)
(* Associative-commutative iso *)
(*---------------------------------------------------------------------------*)
and m_call_op aop toka aargs bop tokb bargs tin =
  let is_commutative_operator = function
    | A.BitOr | A.BitAnd | A.BitXor -> true
    (* TODO: Plus, Mult, ... ? *)
    | A.And | A.Or -> tin.config.commutative_boolop
    | __else__ -> false
  in
  let m_op_default =
    m_arithmetic_operator aop bop >>= fun () -> m_arguments aargs bargs
  in
  (* If this an AC operation we try to perform AC matching, otherwise we perform
   * regular non-AC matching. *)
  if tin.config.ac_matching && aop =*= bop && H.is_associative_operator aop then (
    match
      ( H.ac_matching_nf aop (A.unbracket aargs),
        H.ac_matching_nf bop (B.unbracket bargs) )
    with
    | Some aargs_ac, Some bargs_ac ->
        if is_commutative_operator aop then
          m_ac_op tokb aop aargs_ac bargs_ac tin
        else m_assoc_op tokb aop aargs_ac bargs_ac tin
    | ___else___ ->
        logger#warning
          "Will not perform AC-matching, something went wrong when trying to \
           convert operands to AC normal form: %s ~ %s"
          (A.show_expr (A.Call (A.IdSpecial (A.Op aop, toka), aargs)))
          (B.show_expr (B.Call (B.IdSpecial (B.Op bop, tokb), bargs)));
        m_op_default tin )
  else m_op_default tin

(* Associative-matching of operators.
 *
 * This is very similar to m_list__m_argument where $MVAR acts like $...$MVAR
 * (but cannot match an empty list of arguments).
 *
 * NOTE: There is not need for supporting $...MVAR here, and strictly speaking
 *   it doesn't apply either since we still see the operator as binary.
 *)
and m_assoc_op tok op aargs_ac bargs_ac =
  match (aargs_ac, bargs_ac) with
  | [], [] -> return ()
  (* dots: ..., can also match no argument *)
  | [ A.Ellipsis _i ], [] -> return ()
  (* $MVAR, acting similar to $...MVAR *)
  | (A.N (A.Id ((s, _tok), _idinfo)) as xa) :: xsa, xsb
    when MV.is_metavar_name s ->
      let candidates = inits_and_rest_of_list_empty_ok xsb in
      let rec aux xs =
        match xs with
        | [] -> fail ()
        | (inits, rest) :: xs -> (
            match H.undo_ac_matching_nf tok op inits with
            | Some op_bs' ->
                m_expr xa op_bs'
                >>= (fun () -> m_assoc_op tok op xsa rest)
                >||> aux xs
            | None -> aux xs )
      in
      aux candidates
  | A.Ellipsis i :: xsa, xb :: xsb ->
      (* can match nothing *)
      m_assoc_op tok op xsa (xb :: xsb)
      >||> (* can match more *)
      m_assoc_op tok op (A.Ellipsis i :: xsa) xsb
  | xa :: xsa, xb :: xsb ->
      let* () = m_expr xa xb in
      m_assoc_op tok op xsa xsb
  | _ :: _, [] | [], _ :: _ -> fail ()

(* Associative-Commutative (AC) matching of operators.
 *
 * This for example, will successfully match `a && b && c` against `b && a && c`!
 * It will also match `if (<... b && c ...>) ...` against `if (a && b && c) S`
 * which was not matching before as `a && b && c` is parsed as `(a && b) && c`.
 *
 * NOTE: There is not need for supporting $...MVAR here, and strictly speaking
 *   it doesn't apply either since we still see the operator as binary.
 *
 * BEHAVIOR ISSUES:
 *
 * Even without a deep-expr pattern, `if (b && c) ...` will also match
 * `if (a && b && c) S`. That is, there is an implicit `op ...` added to AC
 * operators. Why? Let's say that we want to match pattern `<... a && b ...>`
 * against `a && (b && c)`, the sub-expressions of `a && (b && c)` are itself,
 * `a`, `b && c`, `b`, and `c`. The only chance to match `a && b` is to do it
 * on `a && (b && c)`, and for that to work we cannot fail when there are
 * operands left to match. TODO: We could try to detect when the AC op-pattern
 * occurs inside a deep-expr and only then assume an implicit `&& ...`.
 *
 * AC-matching of metavariables could lead to some strange behaviors given that
 * we work with ranges. E.g. we can match `a && $X` against `b && a && c` by
 * binding $X to `b && c`, but the range of $X will be that of the whole
 * `b && a && c` expression. Eventually, if we switch to work with the sub-ASTs
 * matched by patterns rather than with their ranges, this will stop being a
 * problem. In the meantime, one can disable AC-matching per rule.
 *
 * Autofix will probably not work well with AC-matching either.
 *
 * PERFORMANCE ISSUES:
 *
 * Note that AC-matching is an NP-complete problem. This is a naive
 * implementation with lots of dumb combinatorial search. We only use
 * AC-matching when we expect it to be fast, otherwise we fall-back to
 * regular non-AC matching.
 *
 * For a more efficient AC matching algorithm, see paper by Steven M. Eker:
 *
 *     "Associative-Commutative Matching Via Bipartite Graph Matching"
 *)
and m_ac_op tok op aargs_ac bargs_ac =
  (* Partitition aargs_ac to separate metavariables and ellipsis (avars) from
   * non-mvar-ish expressions (aapps). *)
  let avars, aapps =
    aargs_ac
    |> List.partition (function
         | A.Ellipsis _ -> true
         | A.N (A.Id ((str, _tok), _id_info)) -> MV.is_metavar_name str
         | ___else___ -> false)
  in
  (* Try to match each aapp with a different barg, this is a 1-to-1 matching.
   * Here we don't expect perf issues on real code, because each aapp will
   * typically only match one bargs_ac, so there should be no combinatorial
   * explosion. Of course one can construct a synthetic example that explodes!
   * E.g. matching a long pattern `A && B && ...` against a very long decision
   * `A && ... && A && B && ... && B && ...` could explode.
   *)
  let bs_left =
    match aapps with
    (* if there are no aapps we don't want to fail *)
    | [] -> m_comb_unit bargs_ac
    | _ -> m_comb_unit bargs_ac |> m_comb_fold (m_comb_1to1 m_expr) aapps
  in
  (* Try to match each variable with a unique disjoint subset of the remaining
   * bs_left, ellipsis (`...`) can match the empty set. This can easily
   * explode so we only perform full AC matching for variables when the
   * number of bs left to match (num_bs_left) is small. Note that an mvar will
   * typically match all subsets of the bs left!!! *)
  let num_bs_left = List.length bargs_ac - List.length aapps in
  let avars_no_end_dots =
    (* An ending ellipsis (...) can be removed without affecting the result
     * but reducing duplicates and improving perf. *)
    match List.rev avars with
    | A.Ellipsis _ :: rev_avars -> List.rev rev_avars
    | ____else____ -> avars
  in
  match avars_no_end_dots with
  (* Nothing to do here, just return. *)
  | [] -> m_comb_flatten bs_left
  | ___many___ when num_bs_left <= 3 ->
      (* AC matching, it explodes easily so use with care! *)
      let m_var x bs' =
        (* `...` can match the empty set, whereas `$MVAR` must much something. *)
        match (x, H.undo_ac_matching_nf tok op bs') with
        | A.Ellipsis _, None -> return ()
        | ___mvar___, None -> fail ()
        | ___mvar___, Some op_bs' -> m_expr x op_bs'
      in
      bs_left
      |> m_comb_fold (m_comb_1toN m_var) avars_no_end_dots
      |> m_comb_flatten
  | ___many___ ->
      (* FALLBACK: We add an ellipsis (`...`) at the end to make sure we match even if
       * there are more bs left than avars, and then we do regular non-AC matching.
       *
       * TODO: Could we first fallback to associative-only matching? It could still
       *       explode but not as easily
       *)
      (* TODO: Issue a proper warning to the user. *)
      logger#warning
        "Restricted AC-matching due to potential blow-up: op=%s avars#=%d \
         bs_left#=%d\n"
        (A.show_operator op) (List.length avars) num_bs_left;
      m_comb_bind bs_left (fun bs' tin ->
          let avars_dots = avars_no_end_dots @ [ A.Ellipsis (A.fake "...") ] in
          let tout =
            m_list__m_argument
              (List.map A.arg avars_dots)
              (List.map B.arg bs') tin
          in
          [ ([], tout) ])
      |> m_comb_flatten

(*****************************************************************************)
(* Type *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_type_]] *)
and m_type_ a b =
  match (a, b) with
  (* equivalence: name resolving! *)
  (* TODO: factorize in a new m_name? *)
  | ( a,
      B.TyN
        (B.Id
          ( idb,
            {
              B.id_resolved =
                {
                  contents =
                    Some
                      ( ( B.ImportedEntity dotted
                        | B.ImportedModule (B.DottedName dotted) ),
                        _sid );
                };
              _;
            } )) ) ->
      m_type_ a (B.TyN (B.Id (idb, B.empty_id_info ())))
      >||> (* try this time a match with the resolved entity *)
      m_type_ a (B.TyN (H.name_of_ids dotted))
  (*s: [[Generic_vs_generic.m_type_]] metavariable case *)
  | A.TyN (A.Id ((str, tok), _id_info)), B.TyN (B.Id (idb, id_infob))
    when MV.is_metavar_name str ->
      envf (str, tok) (MV.Id (idb, Some id_infob))
  (* TODO: TyId vs TyId => add MV.Id *)
  | A.TyN (A.Id ((str, tok), _id_info)), t2 when MV.is_metavar_name str ->
      envf (str, tok) (MV.T t2)
  (*e: [[Generic_vs_generic.m_type_]] metavariable case *)
  (* dots: *)
  | A.TyEllipsis _, _ -> return ()
  (* boilerplate *)
  | A.TyBuiltin a1, B.TyBuiltin b1 -> (m_wrap m_string) a1 b1
  | A.TyFun (a1, a2), B.TyFun (b1, b2) ->
      m_parameters a1 b1 >>= fun () -> m_type_ a2 b2
  | A.TyArray (a1, a2), B.TyArray (b1, b2) ->
      m_bracket (m_option m_expr) a1 b1 >>= fun () -> m_type_ a2 b2
  | A.TyTuple a1, B.TyTuple b1 ->
      (*TODO: m_list__m_type_ ? *)
      (m_bracket (m_list m_type_)) a1 b1
  (*s: [[Generic_vs_generic.m_type_]] boilerplate cases *)
  (* TODO: do via m_name *)
  | A.TyN (A.Id (a1, a2)), B.TyN (B.Id (b1, b2)) ->
      m_ident_and_id_info (a1, a2) (b1, b2)
  | A.TyN (A.IdQualified (a1, a2)), B.TyN (B.IdQualified (b1, b2)) ->
      let* () = m_name_ a1 b1 in
      m_id_info a2 b2
  | A.TyAny a1, B.TyAny b1 -> m_tok a1 b1
  | A.TyNameApply (a1, a2), B.TyNameApply (b1, b2) ->
      m_dotted_name a1 b1 >>= fun () -> m_type_arguments a2 b2
  | A.TyVar a1, B.TyVar b1 -> m_ident a1 b1
  | A.TyPointer (a0, a1), B.TyPointer (b0, b1) ->
      m_tok a0 b0 >>= fun () -> m_type_ a1 b1
  | A.TyRef (a0, a1), B.TyRef (b0, b1) ->
      m_tok a0 b0 >>= fun () -> m_type_ a1 b1
  | A.TyQuestion (a1, a2), B.TyQuestion (b1, b2) ->
      m_type_ a1 b1 >>= fun () -> m_tok a2 b2
  | A.TyRest (a1, a2), B.TyRest (b1, b2) ->
      m_tok a1 b1 >>= fun () -> m_type_ a2 b2
  | A.TyRecordAnon (a0, a1), B.TyRecordAnon (b0, b1) ->
      let* () = m_tok a0 b0 in
      m_bracket m_fields a1 b1
  | A.TyInterfaceAnon (a0, a1), B.TyInterfaceAnon (b0, b1) ->
      let* () = m_tok a0 b0 in
      m_bracket m_fields a1 b1
  | A.TyOr (a1, a2, a3), B.TyOr (b1, b2, b3) ->
      m_type_ a1 b1 >>= fun () ->
      m_tok a2 b2 >>= fun () -> m_type_ a3 b3
  | A.TyAnd (a1, a2, a3), B.TyAnd (b1, b2, b3) ->
      m_type_ a1 b1 >>= fun () ->
      m_tok a2 b2 >>= fun () -> m_type_ a3 b3
  | A.OtherType (a1, a2), B.OtherType (b1, b2) ->
      m_other_type_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.TyBuiltin _, _
  | A.TyFun _, _
  | A.TyNameApply _, _
  | A.TyVar _, _
  | A.TyArray _, _
  | A.TyPointer _, _
  | A.TyTuple _, _
  | A.TyQuestion _, _
  | A.TyRest _, _
  | A.TyN _, _
  | A.TyAny _, _
  | A.TyOr _, _
  | A.TyAnd _, _
  | A.TyRecordAnon _, _
  | A.TyInterfaceAnon _, _
  | A.TyRef _, _
  | A.OtherType _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_type_]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_type_]] *)

(*s: function [[Generic_vs_generic.m_ident_and_type_]] *)
(*e: function [[Generic_vs_generic.m_ident_and_type_]] *)

(*s: function [[Generic_vs_generic.m_type_arguments]] *)
and m_type_arguments a b =
  match (a, b) with a, b -> (m_list m_type_argument) a b

(*e: function [[Generic_vs_generic.m_type_arguments]] *)

(*s: function [[Generic_vs_generic.m_type_argument]] *)
and m_type_argument a b =
  match (a, b) with
  | A.TypeArg a1, B.TypeArg b1 -> m_type_ a1 b1
  | A.TypeWildcard (a1, a2), B.TypeWildcard (b1, b2) ->
      let* () = m_tok a1 b1 in
      m_option m_wildcard a2 b2
  | A.TypeLifetime a1, B.TypeLifetime b1 -> m_ident a1 b1
  | A.OtherTypeArg (a1, a2), B.OtherTypeArg (b1, b2) ->
      m_other_type_argument_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.TypeArg _, _
  | A.TypeWildcard _, _
  | A.TypeLifetime _, _
  | A.OtherTypeArg _, _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_type_argument]] *)
and m_wildcard (a1, a2) (b1, b2) =
  let* () = m_wrap m_bool a1 b1 in
  m_type_ a2 b2

(*s: function [[Generic_vs_generic.m_other_type_operator]] *)
and m_other_type_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_type_operator]] *)
(*s: function [[Generic_vs_generic.m_other_type_argument_operator]] *)
and m_other_type_argument_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_type_argument_operator]] *)
(*****************************************************************************)
(* Attribute *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_keyword_attribute]] *)
and m_keyword_attribute a b =
  match (a, b) with
  (* equivalent: quite JS-specific *)
  | A.Var, (A.Var | A.Let | A.Const) -> return ()
  | _ -> m_other_xxx a b

(*e: function [[Generic_vs_generic.m_keyword_attribute]] *)

(*s: function [[Generic_vs_generic.m_attribute]] *)
and m_attribute a b =
  match (a, b) with
  (*s: [[Generic_vs_generic.m_attribute]] resolving alias case *)
  (* equivalence: name resolving! *)
  (* TODO: factorize with m_name again *)
  | ( a,
      B.NamedAttr
        ( t1,
          B.Id
            ( b1,
              {
                B.id_resolved =
                  {
                    contents =
                      Some
                        ( ( B.ImportedEntity dotted
                          | B.ImportedModule (B.DottedName dotted) ),
                          _sid );
                  };
                _;
              } ),
          b2 ) ) ->
      (* We also allow an unqualified pattern like @Attr to match resolved
       * one like import org.foo.Attr; @Attr *)
      m_attribute a (B.NamedAttr (t1, B.Id (b1, B.empty_id_info ()), b2))
      >||> m_attribute a (B.NamedAttr (t1, H.name_of_ids dotted, b2))
  (*e: [[Generic_vs_generic.m_attribute]] resolving alias case *)
  (* boilerplate *)
  | A.KeywordAttr a1, B.KeywordAttr b1 -> m_wrap m_keyword_attribute a1 b1
  | A.NamedAttr (a0, a1, a2), B.NamedAttr (b0, b1, b2) ->
      m_tok a0 b0 >>= fun () ->
      m_name a1 b1 >>= fun () -> m_bracket m_list__m_argument a2 b2
  | A.OtherAttribute (a1, a2), B.OtherAttribute (b1, b2) ->
      m_other_attribute_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.KeywordAttr _, _ | A.NamedAttr _, _ | A.OtherAttribute _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_attribute]] *)

(*s: function [[Generic_vs_generic.m_other_attribute_operator]] *)
and m_other_attribute_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_attribute_operator]] *)

(*****************************************************************************)
(* Statement list *)
(*****************************************************************************)
(* possibly go deeper when someone wants that a pattern like
 *   ...
 *   bar();
 * to match also calls to bar() deeply as in
 *   foo();
 *   if(true)
 *      bar();
 *
 * When combined with the deep expr, this even allows to match code like
 *  if(true)
 *     x = bar();
 *
 * This is currently very hacky. We just flatten the list of all substmts.
 *
 * alternatives:
 *   - do it the right way by having '...' work on control-flow paths as in
 *     coccinelle
 *
 * todo? we could restrict ourselves to only a few forms?
 *)
(* experimental! *)
and m_stmts_deep ~less_is_ok (xsa : A.stmt list) (xsb : A.stmt list) tin =
  (* shares the cache with m_list__m_stmt *)
  match (tin.cache, xsa, xsb) with
  | Some cache, a :: _, _ :: _ when a.s_use_cache ->
      let tin = { tin with mv = Env.update_min_env tin.mv a } in
      Caching.Cache.match_stmt_list ~access:cache_access ~cache
        ~function_id:CK.Match_deep ~list_kind:CK.Original ~less_is_ok
        ~compute:(m_stmts_deep_uncached ~less_is_ok)
        ~pattern:xsa ~target:xsb tin
  | _ -> m_stmts_deep_uncached ~less_is_ok xsa xsb tin

(*s: function [[Generic_vs_generic.m_stmts_deep]] *)
and m_stmts_deep_uncached ~less_is_ok (xsa : A.stmt list) (xsb : A.stmt list) =
  (* opti: this was the old code:
   *   if !Flag.go_deeper_stmt && (has_ellipsis_stmts xsa)
   *   then
   *   m_list__m_stmt xsa xsb >!> (fun () ->
   *     let xsb' = SubAST_generic.flatten_substmts_of_stmts xsb in
   *     m_list__m_stmt xsa xsb'
   *   )
   *   else m_list__m_stmt xsa xsb
   *
   * but this was really slow on huge files because with a pattern like
   * 'foo(); ...; bar();' we would call flatten_substmts_of_stmts
   * on each sequences in the program, even though foo(); was not
   * matched first.
   * Better to first match the first element, and if it matches and
   * we have a '...' that was not matched on the current sequence,
   * then we try with flatten_substmts_of_stmts.
   *
   * The code below is mostly a copy paste of m_list__m_stmt. We could
   * factorize, but I prefer to control and limit the number of places
   * where we call m_stmts_deep. Once we call m_list__m_stmt, we
   * are in a simpler world where the list of stmts will not grow.
   *)
  match (xsa, xsb) with
  | [], [] -> return ()
  (* less-is-ok:
   * it's ok to have statements after in the concrete code as long as we
   * matched all the statements in the pattern (there is an implicit
   * '...' at the end, in addition to implicit '...' at the beginning
   * handled by kstmts calling the pattern for each subsequences).
   * TODO: sgrep_generic though then display the whole sequence as a match
   * instead of just the relevant part.
   *)
  | [], _ :: _ -> if less_is_ok then return () else fail ()
  (* dots: '...', can also match no statement *)
  | [ { s = A.ExprStmt (A.Ellipsis _i, _); _ } ], [] -> return ()
  | ({ s = A.ExprStmt (A.Ellipsis _i, _); _ } :: _ as xsa), (_ :: _ as xsb) ->
      (* let's first try without going deep *)
      m_list__m_stmt ~list_kind:CK.Original xsa xsb >!> fun () ->
      if_config
        (fun x -> x.go_deeper_stmt)
        ~then_:
          ( match SubAST_generic.flatten_substmts_of_stmts xsb with
          | None -> fail () (* was already flat *)
          | Some (xsb, last_stmt) ->
              m_list__m_stmt ~list_kind:(CK.Flattened_until last_stmt.s_id) xsa
                xsb )
        ~else_:(fail ())
  (* dots: metavars: $...BODY *)
  | ({ s = A.ExprStmt (A.N (A.Id ((s, _), _idinfo)), _); _ } :: _ as xsa), xsb
    when MV.is_metavar_ellipsis s ->
      (* less: for metavariable ellipsis, does it make sense to go deep? *)
      m_list__m_stmt ~list_kind:CK.Original xsa xsb
  (* the general case *)
  | xa :: aas, xb :: bbs ->
      m_stmt xa xb >>= fun () ->
      env_add_matched_stmt xb >>= fun () -> m_stmts_deep ~less_is_ok aas bbs
  | _ :: _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_stmts_deep]] *)
and m_list__m_stmt ?less_is_ok ~list_kind xsa xsb tin =
  (* shares the cache with m_stmts_deep *)
  match (tin.cache, xsa, xsb) with
  | Some cache, a :: _, _ :: _ when a.s_use_cache ->
      let tin = { tin with mv = Env.update_min_env tin.mv a } in
      Caching.Cache.match_stmt_list ~access:cache_access ~cache
        ~function_id:CK.Match_list ~list_kind ~less_is_ok:true
        ~compute:(m_list__m_stmt_uncached ?less_is_ok ~list_kind)
        ~pattern:xsa ~target:xsb tin
  | _ -> m_list__m_stmt_uncached ?less_is_ok ~list_kind xsa xsb tin

(* TODO: factorize with m_list_and_dots less_is_ok = true *)
(* coupling: many of the cases below are similar to the one in
 * m_stmts_deep_uncached.
 * TODO? can we remove the duplication
 *)
(*s: function [[Generic_vs_generic.m_list__m_stmt]] *)
and m_list__m_stmt_uncached ?(less_is_ok = true) ~list_kind (xsa : A.stmt list)
    (xsb : A.stmt list) =
  (* TODO: getting this list every time is redundant *)
  match stmts_may_match xsa xsb with
  | No -> fail ()
  | Maybe -> (
      (*s: [[Generic_vs_generic.m_list__m_stmt]] if [[debug]] *)
      logger#ldebug
        ( lazy
          (spf "m_list__m_stmt_uncached: %d vs %d" (List.length xsa)
             (List.length xsb)) );
      (*e: [[Generic_vs_generic.m_list__m_stmt]] if [[debug]] *)
      match (xsa, xsb) with
      | [], [] -> return ()
      (*s: [[Generic_vs_generic.m_list__m_stmt()]] empty list vs list case *)
      (* less-is-ok:
       * it's ok to have statements after in the concrete code as long as we
       * matched all the statements in the pattern (there is an implicit
       * '...' at the end, in addition to implicit '...' at the beginning
       * handled by kstmts calling the pattern for each subsequences).
       * TODO: sgrep_generic though then display the whole sequence as a match
       * instead of just the relevant part.
       *)
      | [], _ :: _ -> if less_is_ok then return () else fail ()
      (*e: [[Generic_vs_generic.m_list__m_stmt()]] empty list vs list case *)
      (*s: [[Generic_vs_generic.m_list__m_stmt()]] ellipsis cases *)
      (* dots: '...', can also match no statement *)
      | [ { s = A.ExprStmt (A.Ellipsis _i, _); _ } ], [] -> return ()
      | ( { s = A.ExprStmt (A.Ellipsis _i, _); _ } :: xsa_tail,
          (xb :: xsb_tail as xsb) ) ->
          (* can match nothing *)
          m_list__m_stmt ~list_kind xsa_tail xsb
          >||> (* can match more *)
          ( env_add_matched_stmt xb >>= fun () ->
            m_list__m_stmt ~list_kind xsa xsb_tail )
      (*e: [[Generic_vs_generic.m_list__m_stmt()]] ellipsis cases *)
      (* dots: metavars: $...BODY *)
      | { s = A.ExprStmt (A.N (A.Id ((s, tok), _idinfo)), _); _ } :: xsa, xsb
        when MV.is_metavar_ellipsis s ->
          (* can match 0 or more arguments *)
          let candidates = inits_and_rest_of_list_empty_ok xsb in
          let rec aux xs =
            match xs with
            | [] -> fail ()
            | (inits, rest) :: xs ->
                envf (s, tok) (MV.Ss inits)
                >>= (fun () ->
                      (* less: env_add_matched_stmt ?? *)
                      (* when we use { $...BODY }, we don't have an implicit
                       * ... after, so we use less_is_ok:false here
                       *)
                      m_list__m_stmt ~less_is_ok:false ~list_kind xsa rest)
                >||> aux xs
          in
          aux candidates
      (* the general case *)
      | xa :: aas, xb :: bbs ->
          m_stmt xa xb >>= fun () ->
          env_add_matched_stmt xb >>= fun () ->
          m_list__m_stmt ~list_kind aas bbs
      | _ :: _, _ -> fail () )

(*e: function [[Generic_vs_generic.m_list__m_stmt]] *)

(*****************************************************************************)
(* Statement *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_stmt]] *)
and m_stmt a b =
  match (a.s, b.s) with
  (* the order of the matches matters! take care! *)
  (*s: [[Generic_vs_generic.m_stmt()]] disjunction case *)
  (* equivalence: user-defined equivalence! *)
  | A.DisjStmt (a1, a2), _b -> m_stmt a1 b >||> m_stmt a2 b
  (*e: [[Generic_vs_generic.m_stmt()]] disjunction case *)
  (*s: [[Generic_vs_generic.m_stmt()]] metavariable case *)
  (* metavar: *)
  (* Note that we can't consider $S a statement metavariable only if the
   * semicolon is a fake one. Indeed in many places we have patterns
   * like 'if(...) $S;' because 'if(...) $S' would not parse.
   * alt: parse if(...) $S without the ending semicolon?
   * But at least we can try to match $S as a statement metavar
   * _or_ an expression metavar with >||>. below
   *)
  | A.ExprStmt ((A.N (A.Id ((str, tok), _id_info)) as suba), sc), _b
    when MV.is_metavar_name str -> (
      envf (str, tok) (MV.S b)
      >||>
      match b.s with
      | B.ExprStmt (subb, _) when not (Parse_info.is_fake sc) ->
          m_expr suba subb
      | _ -> fail () )
  (*e: [[Generic_vs_generic.m_stmt()]] metavariable case *)
  (*s: [[Generic_vs_generic.m_stmt()]] ellipsis cases *)
  (* dots: '...' can to match any statememt *)
  | A.ExprStmt (A.Ellipsis _i, _), _b -> return ()
  (*x: [[Generic_vs_generic.m_stmt()]] ellipsis cases *)
  | A.Return (a0, a1, asc), B.Return (b0, b1, bsc) ->
      let* () = m_tok a0 b0 in
      let* () = m_option_ellipsis_ok m_expr a1 b1 in
      m_tok asc bsc
  (*e: [[Generic_vs_generic.m_stmt()]] ellipsis cases *)
  (*s: [[Generic_vs_generic.m_stmt()]] deep matching cases *)
  (* deeper: go deep by default implicitly (no need for explicit <... ...>) *)
  | A.ExprStmt (a1, a2), B.ExprStmt (b1, b2) ->
      m_expr_deep a1 b1 >>= fun () -> m_tok a2 b2
  (*x: [[Generic_vs_generic.m_stmt()]] deep matching cases *)
  (* opti: specialization to avoid going in the deep stmt matching!
   * TODO: we should not need this; '...' should not enumerate all
   * possible subset of stmt list and take forever.
   * Note that as a side effect it returns also less equivalent
   * matches (which again, should not happen), which used to introduce
   * some regressions (see tests/OTHER/rules/regression_uniq...) but this
   * has been fixed now.
   *)
  | A.Block (_, [ { s = A.ExprStmt (A.Ellipsis _i, _); _ } ], _), B.Block _b1 ->
      return ()
  (* opti: another specialization; again we should not need it *)
  | ( A.Block
        ( _,
          [
            { s = A.ExprStmt (A.Ellipsis _, _); _ };
            a;
            { s = A.ExprStmt (A.Ellipsis _, _); _ };
          ],
          _ ),
      B.Block (_, bs, _) ) ->
      let bs =
        match SubAST_generic.flatten_substmts_of_stmts bs with
        (* already flat  *)
        | None -> bs
        | Some (xs, _) -> xs
      in
      or_list m_stmt a bs
  (* the general case *)
  (* ... will now allow a subset of stmts (less_is_ok = false here) *)
  | A.Block a1, B.Block b1 -> m_bracket (m_stmts_deep ~less_is_ok:false) a1 b1
  (*e: [[Generic_vs_generic.m_stmt()]] deep matching cases *)
  (*s: [[Generic_vs_generic.m_stmt()]] builtin equivalences cases *)
  (* equivalence: vardef ==> assign, and go deep *)
  | ( A.ExprStmt (a1, _),
      B.DefStmt (ent, B.VarDef ({ B.vinit = Some _; _ } as def)) ) ->
      let b1 = H.vardef_to_assign (ent, def) in
      m_expr_deep a1 b1
  (*x: [[Generic_vs_generic.m_stmt()]] builtin equivalences cases *)
  (* equivalence: *)
  | A.ExprStmt (a1, _), B.Return (_, Some b1, _) -> m_expr_deep a1 b1
  (*e: [[Generic_vs_generic.m_stmt()]] builtin equivalences cases *)
  (* boilerplate *)
  | A.If (a0, a1, a2, a3), B.If (b0, b1, b2, b3) ->
      m_tok a0 b0 >>= fun () ->
      (* too many regressions doing m_expr_deep by default; Use DeepEllipsis *)
      m_expr a1 b1 >>= fun () ->
      m_block a2 b2 >>= fun () ->
      (* less-is-more: *)
      m_option_none_can_match_some m_block a3 b3
  | A.While (a0, a1, a2), B.While (b0, b1, b2) ->
      m_tok a0 b0 >>= fun () ->
      m_expr a1 b1 >>= fun () -> m_stmt a2 b2
  (*s: [[Generic_vs_generic.m_stmt]] boilerplate cases *)
  | A.DefStmt a1, B.DefStmt b1 -> m_definition a1 b1
  | A.DirectiveStmt a1, B.DirectiveStmt b1 -> m_directive a1 b1
  (*x: [[Generic_vs_generic.m_stmt]] boilerplate cases *)
  | A.DoWhile (a0, a1, a2), B.DoWhile (b0, b1, b2) ->
      m_tok a0 b0 >>= fun () ->
      m_stmt a1 b1 >>= fun () -> m_expr a2 b2
  | A.For (a0, a1, a2), B.For (b0, b1, b2) ->
      m_tok a0 b0 >>= fun () ->
      m_for_header a1 b1 >>= fun () -> m_stmt a2 b2
  | A.Switch (at, a1, a2), B.Switch (bt, b1, b2) ->
      m_tok at bt >>= fun () ->
      m_option m_expr a1 b1 >>= fun () -> m_case_clauses a2 b2
  | A.Continue (a0, a1, asc), B.Continue (b0, b1, bsc) ->
      let* () = m_tok a0 b0 in
      let* () = m_label_ident a1 b1 in
      m_tok asc bsc
  | A.Break (a0, a1, asc), B.Break (b0, b1, bsc) ->
      let* () = m_tok a0 b0 in
      let* () = m_label_ident a1 b1 in
      m_tok asc bsc
  | A.Label (a1, a2), B.Label (b1, b2) ->
      m_label a1 b1 >>= fun () -> m_stmt a2 b2
  | A.Goto (a0, a1), B.Goto (b0, b1) -> m_tok a0 b0 >>= fun () -> m_label a1 b1
  | A.Throw (a0, a1, asc), B.Throw (b0, b1, bsc) ->
      let* () = m_tok a0 b0 in
      let* () = m_expr a1 b1 in
      m_tok asc bsc
  | A.Try (a0, a1, a2, a3), B.Try (b0, b1, b2, b3) ->
      let* () = m_tok a0 b0 in
      let* () = m_stmt a1 b1 in
      let* () = (m_list m_catch) a2 b2 in
      (m_option m_finally) a3 b3
  | A.Assert (a0, a1, a2, asc), B.Assert (b0, b1, b2, bsc) ->
      let* () = m_tok a0 b0 in
      let* () = m_expr a1 b1 in
      let* () = (m_option m_expr) a2 b2 in
      m_tok asc bsc
  | A.OtherStmt (a1, a2), B.OtherStmt (b1, b2) ->
      m_other_stmt_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.OtherStmtWithStmt (a1, a2, a3), B.OtherStmtWithStmt (b1, b2, b3) ->
      m_other_stmt_with_stmt_operator a1 b1 >>= fun () ->
      m_option m_expr a2 b2 >>= fun () -> m_stmt a3 b3
  | A.WithUsingResource (a1, a2, a3), B.WithUsingResource (b1, b2, b3) ->
      m_tok a1 b1 >>= fun () ->
      m_stmt a2 b2 >>= fun () -> m_stmt a3 b3
  | A.ExprStmt _, _
  | A.DefStmt _, _
  | A.DirectiveStmt _, _
  | A.Block _, _
  | A.If _, _
  | A.While _, _
  | A.DoWhile _, _
  | A.For _, _
  | A.Switch _, _
  | A.Return _, _
  | A.Continue _, _
  | A.Break _, _
  | A.Label _, _
  | A.Goto _, _
  | A.Throw _, _
  | A.Try _, _
  | A.Assert _, _
  | A.OtherStmt _, _
  | A.OtherStmtWithStmt _, _
  | A.WithUsingResource _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_stmt]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_stmt]] *)
and m_case_clauses a b =
  let _has_ellipsis, a = has_case_ellipsis_and_filter_ellipsis a in
  (* todo? always implicit ...?
   * todo? do in any order? In theory the order of the cases matter, but
   * in a semgrep context, people probably don't want to find
   * specific cases in a specific order.
   *)
  m_list_in_any_order ~less_is_ok:true m_case_and_body a b

(*s: function [[Generic_vs_generic.m_for_header]] *)
and m_for_header a b =
  match (a, b) with
  (* dots: *)
  | A.ForEllipsis _, _ -> return ()
  | A.ForClassic (a1, a2, a3), B.ForClassic (b1, b2, b3) ->
      (m_list m_for_var_or_expr) a1 b1 >>= fun () ->
      m_option m_expr a2 b2 >>= fun () -> m_option m_expr a3 b3
  | A.ForEach (a1, at, a2), B.ForEach (b1, bt, b2) ->
      m_pattern a1 b1 >>= fun () ->
      m_tok at bt >>= fun () -> m_expr a2 b2
  | A.ForIn (a1, a2), B.ForIn (b1, b2) ->
      (m_list m_for_var_or_expr) a1 b1 >>= fun () -> m_list m_expr a2 b2
  | A.ForClassic _, _ | A.ForEach _, _ | A.ForIn _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_for_header]] *)
and m_block a b =
  match (a.s, b.s) with
  | A.Block _, B.Block _ -> m_stmt a b
  | A.Block (_, [ a_stmt ], _), _ -> m_stmt a_stmt b
  | _, B.Block (_, [ b_stmt ], _) -> m_stmt a b_stmt
  | _, _ -> m_stmt a b

(*s: function [[Generic_vs_generic.m_for_var_or_expr]] *)
and m_for_var_or_expr a b =
  match (a, b) with
  | A.ForInitVar (a1, a2), B.ForInitVar (b1, b2) ->
      m_entity a1 b1 >>= fun () -> m_variable_definition a2 b2
  | A.ForInitExpr a1, B.ForInitExpr b1 -> m_expr a1 b1
  | A.ForInitVar _, _ | A.ForInitExpr _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_for_var_or_expr]] *)

(*s: function [[Generic_vs_generic.m_label]] *)
and m_label a b = match (a, b) with a, b -> m_ident a b

(*e: function [[Generic_vs_generic.m_label]] *)

(*s: function [[Generic_vs_generic.m_catch]] *)
and m_catch a b =
  match (a, b) with
  | (at, a1, a2), (bt, b1, b2) ->
      m_tok at bt >>= fun () ->
      m_pattern a1 b1 >>= fun () -> m_stmt a2 b2

(*e: function [[Generic_vs_generic.m_catch]] *)

(*s: function [[Generic_vs_generic.m_finally]] *)
and m_finally a b =
  match (a, b) with (at, a), (bt, b) -> m_tok at bt >>= fun () -> m_stmt a b

(*e: function [[Generic_vs_generic.m_finally]] *)

(*s: function [[Generic_vs_generic.m_case_and_body]] *)
and m_case_and_body a b =
  match (a, b) with
  | CasesAndBody (a1, a2), CasesAndBody (b1, b2) ->
      (m_list m_case) a1 b1 >>= fun () -> m_stmt a2 b2
  | CaseEllipsis _, CasesAndBody _ -> return ()
  | CasesAndBody _, _ | CaseEllipsis _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_case_and_body]] *)

(*s: function [[Generic_vs_generic.m_case]] *)
and m_case a b =
  match (a, b) with
  | A.Case (a0, a1), B.Case (b0, b1) ->
      m_tok a0 b0 >>= fun () -> m_pattern a1 b1
  | A.CaseEqualExpr (a0, a1), B.CaseEqualExpr (b0, b1) ->
      m_tok a0 b0 >>= fun () -> m_expr a1 b1
  | A.Default a0, B.Default b0 -> m_tok a0 b0
  | A.Case _, _ | A.Default _, _ | A.CaseEqualExpr _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_case]] *)

(*s: function [[Generic_vs_generic.m_other_stmt_operator]] *)
and m_other_stmt_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_stmt_operator]] *)

(*s: function [[Generic_vs_generic.m_other_stmt_with_stmt_operator]] *)
and m_other_stmt_with_stmt_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_stmt_with_stmt_operator]] *)

(*****************************************************************************)
(* Pattern *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_pattern]] *)
and m_pattern a b =
  match (a, b) with
  (*s: [[Generic_vs_generic.m_pattern()]] disjunction case *)
  (* equivalence: user-defined equivalence! *)
  | A.DisjPat (a1, a2), b -> m_pattern a1 b >||> m_pattern a2 b
  (*e: [[Generic_vs_generic.m_pattern()]] disjunction case *)
  (*s: [[Generic_vs_generic.m_pattern()]] metavariable case *)
  (* metavar: *)
  (* less: A.PatId vs B.PatId? Use MV.Id then ? *)
  | A.PatId ((str, tok), _id_info), b2 when MV.is_metavar_name str -> (
      try
        let e2 = H.pattern_to_expr b2 in
        envf (str, tok) (MV.E e2)
        (* this can happen with PatAs in exception handler in Python *)
      with H.NotAnExpr ->
        envf (str, tok) (MV.P b2)
        (*e: [[Generic_vs_generic.m_pattern()]] metavariable case *) )
  (* dots: *)
  | A.PatEllipsis _, _ -> return ()
  (* boilerplate *)
  (*s: [[Generic_vs_generic.m_pattern]] boilerplate cases *)
  | A.PatId (a1, a2), B.PatId (b1, b2) ->
      m_ident a1 b1 >>= fun () -> m_id_info a2 b2
  | A.PatLiteral a1, B.PatLiteral b1 -> m_literal a1 b1
  | A.PatType a1, B.PatType b1 -> m_type_ a1 b1
  | A.PatConstructor (a1, a2), B.PatConstructor (b1, b2) ->
      m_dotted_name a1 b1 >>= fun () -> (m_list m_pattern) a2 b2
  | A.PatTuple a1, B.PatTuple b1 -> m_bracket (m_list m_pattern) a1 b1
  | A.PatList a1, B.PatList b1 -> m_bracket (m_list m_pattern) a1 b1
  | A.PatRecord a1, B.PatRecord b1 -> m_bracket (m_list m_field_pattern) a1 b1
  | A.PatKeyVal (a1, a2), B.PatKeyVal (b1, b2) ->
      m_pattern a1 b1 >>= fun () -> m_pattern a2 b2
  | A.PatUnderscore a1, B.PatUnderscore b1 -> m_tok a1 b1
  | A.PatDisj (a1, a2), B.PatDisj (b1, b2) ->
      m_pattern a1 b1 >>= fun () -> m_pattern a2 b2
  | A.PatAs (a1, (a2, a3)), B.PatAs (b1, (b2, b3)) ->
      m_pattern a1 b1 >>= fun () -> m_ident_and_id_info (a2, a3) (b2, b3)
  | A.PatTyped (a1, a2), B.PatTyped (b1, b2) ->
      m_pattern a1 b1 >>= fun () -> m_type_ a2 b2
  | A.PatVar (a1, a2), B.PatVar (b1, b2) ->
      m_type_ a1 b1 >>= fun () -> m_option m_ident_and_id_info a2 b2
  | A.PatWhen (a1, a2), B.PatWhen (b1, b2) ->
      m_pattern a1 b1 >>= fun () -> m_expr a2 b2
  | A.OtherPat (a1, a2), B.OtherPat (b1, b2) ->
      m_other_pattern_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.PatId _, _
  | A.PatLiteral _, _
  | A.PatConstructor _, _
  | A.PatTuple _, _
  | A.PatList _, _
  | A.PatRecord _, _
  | A.PatKeyVal _, _
  | A.PatUnderscore _, _
  | A.PatDisj _, _
  | A.PatWhen _, _
  | A.PatAs _, _
  | A.PatTyped _, _
  | A.OtherPat _, _
  | A.PatType _, _
  | A.PatVar _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_pattern]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_pattern]] *)

(*s: function [[Generic_vs_generic.m_field_pattern]] *)
and m_field_pattern a b =
  match (a, b) with
  | (a1, a2), (b1, b2) -> m_dotted_name a1 b1 >>= fun () -> m_pattern a2 b2

(*e: function [[Generic_vs_generic.m_field_pattern]] *)

(*s: function [[Generic_vs_generic.m_other_pattern_operator]] *)
and m_other_pattern_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_pattern_operator]] *)

(*****************************************************************************)
(* Definitions *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_definition]] *)
and m_definition a b =
  match (a, b) with
  | (a1, a2), (b1, b2) ->
      (* subtle: if you change the order here, so that we execute m_entity
       * only when the definition_kind matches, this helps to avoid
       * calls to ocamllsp when you put a type constraint on a function.
       * Indeed, we will call ocamllsp only for FuncDef.
       * This also avoids to call ocamllsp on type definition entities,
       * which can leads to errors in type_of_string.
       *)
      let* () = m_entity a1 b1 in
      let* () = m_definition_kind a2 b2 in
      return ()

(*e: function [[Generic_vs_generic.m_definition]] *)

(*s: function [[Generic_vs_generic.m_entity]] *)
and m_entity a b =
  match (a, b) with
  (* bugfix: when we use a metavar to match an entity, as in $X(...): ...
   * and later we use $X again to match a name, the $X is first an ident and
   * later an expression, which would prevent a match. Instead we need to
   * make $X an expression early on.
   * update: actually better to use a special MV.Id for that.
   *)
  | ( { A.name = a1; attrs = a2; tparams = a4 },
      { B.name = b1; attrs = b2; tparams = b4 } ) ->
      m_name_or_dynamic a1 b1 >>= fun () ->
      m_list_in_any_order ~less_is_ok:true m_attribute a2 b2 >>= fun () ->
      (m_list m_type_parameter) a4 b4

(*e: function [[Generic_vs_generic.m_entity]] *)

(*s: function [[Generic_vs_generic.m_definition_kind]] *)
and m_definition_kind a b =
  match (a, b) with
  (* boilerplate *)
  | A.FuncDef a1, B.FuncDef b1 -> m_function_definition a1 b1
  | A.VarDef a1, B.VarDef b1 -> m_variable_definition a1 b1
  | A.FieldDefColon a1, B.FieldDefColon b1 -> m_variable_definition a1 b1
  | A.ClassDef a1, B.ClassDef b1 -> m_class_definition a1 b1
  (*s: [[Generic_vs_generic.m_definition_kind]] boilerplate cases *)
  | A.TypeDef a1, B.TypeDef b1 -> m_type_definition a1 b1
  | A.ModuleDef a1, B.ModuleDef b1 -> m_module_definition a1 b1
  | A.MacroDef a1, B.MacroDef b1 -> m_macro_definition a1 b1
  | A.Signature a1, B.Signature b1 -> m_type_ a1 b1
  | A.UseOuterDecl a1, B.UseOuterDecl b1 -> m_tok a1 b1
  | A.FuncDef _, _
  | A.VarDef _, _
  | A.ClassDef _, _
  | A.TypeDef _, _
  | A.ModuleDef _, _
  | A.MacroDef _, _
  | A.Signature _, _
  | A.UseOuterDecl _, _
  | A.FieldDefColon _, _
  | A.OtherDef _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_definition_kind]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_definition_kind]] *)

(*s: function [[Generic_vs_generic.m_type_parameter_constraint]] *)
and m_type_parameter_constraint a b =
  match (a, b) with
  | A.Extends a1, B.Extends b1 -> m_type_ a1 b1
  | A.HasConstructor a1, B.HasConstructor b1 -> m_tok a1 b1
  | A.OtherTypeParam (a1, a2), B.OtherTypeParam (b1, b2) ->
      m_other_type_parameter_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.Extends _, _ | A.HasConstructor _, _ | A.OtherTypeParam _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_type_parameter_constraint]] *)
and m_other_type_parameter_operator = m_other_xxx

(*s: function [[Generic_vs_generic.m_type_parameter_constraints]] *)
and m_type_parameter_constraints a b =
  match (a, b) with a, b -> (m_list m_type_parameter_constraint) a b

(*e: function [[Generic_vs_generic.m_type_parameter_constraints]] *)

(*s: function [[Generic_vs_generic.m_type_parameter]] *)
and m_type_parameter a b =
  match (a, b) with
  | (a1, a2), (b1, b2) ->
      m_ident a1 b1 >>= fun () -> m_type_parameter_constraints a2 b2

(*e: function [[Generic_vs_generic.m_type_parameter]] *)

(* ------------------------------------------------------------------------- *)
(* Function (or method) definition *)
(* ------------------------------------------------------------------------- *)

(* iso: we don't care if it's a Function or Arrow *)
and m_function_kind _ _ = return ()

(*s: function [[Generic_vs_generic.m_function_definition]] *)
and m_function_definition a b =
  match (a, b) with
  | ( { A.fparams = a1; frettype = a2; fbody = a3; fkind = a4 },
      { B.fparams = b1; frettype = b2; fbody = b3; fkind = b4 } ) ->
      m_parameters a1 b1 >>= fun () ->
      (m_option_none_can_match_some m_type_) a2 b2 >>= fun () ->
      m_stmt a3 b3 >>= fun () -> m_wrap m_function_kind a4 b4

(*e: function [[Generic_vs_generic.m_function_definition]] *)

(*s: function [[Generic_vs_generic.m_parameters]] *)
and m_parameters a b =
  m_list_with_dots m_parameter
    (function A.ParamEllipsis _ -> true | _ -> false)
    false (* empty list can not match non-empty list *) a b

(*e: function [[Generic_vs_generic.m_parameters]] *)

(*s: function [[Generic_vs_generic.m_parameter]] *)
and m_parameter a b =
  match (a, b) with
  (* boilerplate *)
  | A.ParamClassic a1, B.ParamClassic b1 -> m_parameter_classic a1 b1
  | A.ParamRest (a1, a2), B.ParamRest (b1, b2) ->
      let* () = m_tok a1 b1 in
      m_parameter_classic a2 b2
  | A.ParamHashSplat (a1, a2), B.ParamHashSplat (b1, b2) ->
      let* () = m_tok a1 b1 in
      m_parameter_classic a2 b2
  (*s: [[Generic_vs_generic.m_parameter]] boilerplate cases *)
  | A.ParamPattern a1, B.ParamPattern b1 -> m_pattern a1 b1
  | A.OtherParam (a1, a2), B.OtherParam (b1, b2) ->
      m_other_parameter_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.ParamEllipsis a1, B.ParamEllipsis b1 -> m_tok a1 b1
  | A.ParamClassic _, _
  | A.ParamPattern _, _
  | A.ParamRest _, _
  | A.ParamHashSplat _, _
  | A.ParamEllipsis _, _
  | A.OtherParam _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_parameter]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_parameter]] *)

(*s: function [[Generic_vs_generic.m_parameter_classic]] *)
and m_parameter_classic a b =
  match (a, b) with
  (*s: [[Generic_vs_generic.m_parameter_classic]] metavariable case *)
  (* bugfix: when we use a metavar to match a parameter, as in foo($X): ...
   * and later we use $X again to match a name, the $X is first an ident and
   * later an expression, which would prevent a match. Instead we need to
   * make $X an expression early on
   *)
  | ( { A.pname = Some a1; pdefault = a2; ptype = a3; pattrs = a4; pinfo = a5 },
      { B.pname = Some b1; pdefault = b2; ptype = b3; pattrs = b4; pinfo = b5 }
    ) ->
      m_ident_and_id_info (a1, a5) (b1, b5) >>= fun () ->
      (m_option m_expr) a2 b2 >>= fun () ->
      (m_type_option_with_hook b1) a3 b3 >>= fun () ->
      m_list_in_any_order ~less_is_ok:true m_attribute a4 b4
  (*e: [[Generic_vs_generic.m_parameter_classic]] metavariable case *)
  (* boilerplate *)
  | ( { A.pname = a1; pdefault = a2; ptype = a3; pattrs = a4; pinfo = a5 },
      { B.pname = b1; pdefault = b2; ptype = b3; pattrs = b4; pinfo = b5 } ) ->
      (m_option m_ident) a1 b1 >>= fun () ->
      (m_option m_expr) a2 b2 >>= fun () ->
      (m_option_none_can_match_some m_type_) a3 b3 >>= fun () ->
      m_list_in_any_order ~less_is_ok:true m_attribute a4 b4 >>= fun () ->
      m_id_info a5 b5

(*e: function [[Generic_vs_generic.m_parameter_classic]] *)

(*s: function [[Generic_vs_generic.m_other_parameter_operator]] *)
and m_other_parameter_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_parameter_operator]] *)

(* ------------------------------------------------------------------------- *)
(* Variable definition *)
(* ------------------------------------------------------------------------- *)

(*s: function [[Generic_vs_generic.m_variable_definition]] *)
and m_variable_definition a b =
  match (a, b) with
  (* boilerplate *)
  | { A.vinit = a1; vtype = a2 }, { B.vinit = b1; vtype = b2 } ->
      (m_option m_expr) a1 b1 >>= fun () ->
      (m_option_none_can_match_some m_type_) a2 b2

(*e: function [[Generic_vs_generic.m_variable_definition]] *)

(* ------------------------------------------------------------------------- *)
(* Field definition and use *)
(* ------------------------------------------------------------------------- *)

(* As opposed to statements, the order of fields should not matter.
 *
 * We actually filter the '...' and use a less-is-ok approach.
 * Indeed '...' are not really useful, and in some patological cases they
 * were actually leading to the use a tons of memory. Indeed, in certain
 * files containing a long list of fields (like 3000 static fields),
 * the classic use of >||> to handle Ellipsis variations were stressing
 * a lot the engine. Simpler to just filter them.
 *)
(*s: function [[Generic_vs_generic.m_fields]] *)
and m_fields (xsa : A.field list) (xsb : A.field list) =
  (* let's filter the '...' *)
  let xsa =
    xsa
    |> Common.exclude (function
         | A.FieldStmt { s = A.ExprStmt (A.Ellipsis _, _); _ } -> true
         | _ -> false)
  in
  m_list__m_field xsa xsb

(*e: function [[Generic_vs_generic.m_fields]] *)

(* less: mix of m_list_and_dots and m_list_unordered_keys, hard to factorize *)
(*s: function [[Generic_vs_generic.m_list__m_field]] *)
and m_list__m_field (xsa : A.field list) (xsb : A.field list) =
  logger#ldebug
    (lazy (spf "m_list__m_field:%d vs %d" (List.length xsa) (List.length xsb)));
  match (xsa, xsb) with
  | [], [] -> return ()
  (*s: [[Generic_vs_generic.m_list__m_field()]] empty list vs list case *)
  (* less-is-ok:
   * it's ok to have fields after in the concrete code as long as we
   * matched all the fields in the pattern.
   * TODO? should we impose to use '...' if you allow extra fields?
   *)
  | [], _ :: _ -> return ()
  (*e: [[Generic_vs_generic.m_list__m_field()]] empty list vs list case *)
  (*s: [[Generic_vs_generic.m_list__m_field()]] ellipsis cases *)
  | A.FieldStmt { s = A.ExprStmt (A.Ellipsis _, _); _ } :: _, _ ->
      raise Impossible
  (*e: [[Generic_vs_generic.m_list__m_field()]] ellipsis cases *)
  (*s: [[Generic_vs_generic.m_list__m_field()]] [[DefStmt]] pattern case *)
  (* Note that we restrict the match-a-field-at-any-position only for
   * definitions, which allows us to optimize things a little bit
   * by using split_when below.
   * However, if the field use a metavariable, we need to use
   * the more expensive all_elem_and_rest_of_list.
   *
   * bugfix: In python we used to not do this match-a-field-at-any-pos
   * for code like 'class $FOO: $VAR = 1' because those were originally
   * not parsed as DefStmt but as Assign.
   * alt: keep them as Assign, but always do the all_elem_and_rest_of_list
   *)
  | ( ( A.FieldStmt
          {
            s = A.DefStmt (({ A.name = A.EN (A.Id ((s1, _), _)); _ }, _) as adef);
            _;
          } as a )
      :: xsa,
      xsb ) -> (
      if MV.is_metavar_name s1 || Pattern.is_regexp_string s1 then
        (*s: [[Generic_vs_generic.m_list__m_field()]] in [[DefStmt]] case if metavar field *)
        let candidates = all_elem_and_rest_of_list xsb in
        (* less: could use a fold *)
        let rec aux xs =
          match xs with
          | [] -> fail ()
          | (b, xsb) :: xs ->
              m_field a b
              >>= (fun () -> m_list__m_field xsa (lazy_rest_of_list xsb))
              >||> aux xs
        in
        aux candidates
        (*e: [[Generic_vs_generic.m_list__m_field()]] in [[DefStmt]] case if metavar field *)
      else
        try
          let before, there, after =
            xsb
            |> Common2.split_when (function
                 | A.FieldStmt
                     {
                       s =
                         A.DefStmt
                           ({ B.name = B.EN (B.Id ((s2, _tok), _)); _ }, _);
                       _;
                     }
                   when s2 = s1 ->
                     true
                 | _ -> false)
          in
          match there with
          | A.FieldStmt { s = A.DefStmt bdef; _ } ->
              m_definition adef bdef >>= fun () ->
              m_list__m_field xsa (before @ after)
          | _ -> raise Impossible
        with Not_found -> fail () )
  (*e: [[Generic_vs_generic.m_list__m_field()]] [[DefStmt]] pattern case *)
  (* the general case *)
  (* todo? ideally we should never reach this part and always allow
   * to match a field at any position.
   *)
  | xa :: aas, xb :: bbs -> m_field xa xb >>= fun () -> m_list__m_field aas bbs
  | _ :: _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_list__m_field]] *)

(*s: function [[Generic_vs_generic.m_field]] *)
and m_field a b =
  match (a, b) with
  (* boilerplate *)
  | A.FieldStmt a1, B.FieldStmt b1 -> m_stmt a1 b1
  (*s: [[Generic_vs_generic.m_field]] boilerplate cases *)
  | A.FieldSpread (a0, a1), B.FieldSpread (b0, b1) ->
      m_tok a0 b0 >>= fun () -> m_expr a1 b1
  | A.FieldSpread _, _ | A.FieldStmt _, _ -> fail ()

(*e: [[Generic_vs_generic.m_field]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_field]] *)

(* ------------------------------------------------------------------------- *)
(* Type definition *)
(* ------------------------------------------------------------------------- *)

(*s: function [[Generic_vs_generic.m_type_definition]] *)
and m_type_definition a b =
  match (a, b) with
  | { A.tbody = a1 }, { B.tbody = b1 } -> m_type_definition_kind a1 b1

(*e: function [[Generic_vs_generic.m_type_definition]] *)

(*s: function [[Generic_vs_generic.m_type_definition_kind]] *)
and m_type_definition_kind a b =
  match (a, b) with
  | A.OrType a1, B.OrType b1 -> (m_list m_or_type) a1 b1
  | A.AndType a1, B.AndType b1 -> m_bracket m_fields a1 b1
  | A.AliasType a1, B.AliasType b1 -> m_type_ a1 b1
  | A.NewType a1, B.NewType b1 -> m_type_ a1 b1
  | A.Exception (a1, a2), B.Exception (b1, b2) ->
      m_ident a1 b1 >>= fun () ->
      (* TODO: m_list__m_type_ ? *)
      (m_list m_type_) a2 b2
  | A.OtherTypeKind (a1, a2), B.OtherTypeKind (b1, b2) ->
      m_other_type_kind_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.OrType _, _
  | A.AndType _, _
  | A.AliasType _, _
  | A.Exception _, _
  | A.NewType _, _
  | A.OtherTypeKind _, _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_type_definition_kind]] *)

(*s: function [[Generic_vs_generic.m_or_type]] *)
and m_or_type a b =
  match (a, b) with
  | A.OrConstructor (a1, a2), B.OrConstructor (b1, b2) ->
      m_ident a1 b1 >>= fun () ->
      (* TODO: m_list__m_type_ ? *)
      (m_list m_type_) a2 b2
  | A.OrEnum (a1, a2), B.OrEnum (b1, b2) ->
      m_ident a1 b1 >>= fun () -> m_option m_expr a2 b2
  | A.OrUnion (a1, a2), B.OrUnion (b1, b2) ->
      m_ident a1 b1 >>= fun () -> m_type_ a2 b2
  | A.OtherOr (a1, a2), B.OtherOr (b1, b2) ->
      m_other_or_type_element_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.OrConstructor _, _ | A.OrEnum _, _ | A.OrUnion _, _ | A.OtherOr _, _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_or_type]] *)

(*s: function [[Generic_vs_generic.m_other_type_kind_operator]] *)
and m_other_type_kind_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_type_kind_operator]] *)

(*s: function [[Generic_vs_generic.m_other_or_type_element_operator]] *)
and m_other_or_type_element_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_or_type_element_operator]] *)

(*s: function [[Generic_vs_generic.m_list__m_type_]] *)
and m_list__m_type_ (xsa : A.type_ list) (xsb : A.type_ list) =
  m_list_with_dots m_type_
    (* dots: '...', this is very Python Specific I think *)
      (function
      | A.OtherType (A.OT_Arg, [ A.Ar (A.Arg (A.Ellipsis _i)) ]) -> true
      | _ -> false)
    (* less-is-ok: it's ok to not specify all the parents I think *)
    true (* empty list can not match non-empty list *) xsa xsb

(*e: function [[Generic_vs_generic.m_list__m_type_]] *)
and m_list__m_type_any_order (xsa : A.type_ list) (xsb : A.type_ list) =
  (* TODO? filter existing ellipsis?
   * let _has_ellipsis, xsb = has_ellipsis_and_filter_ellipsis xsb in *)
  (* always implicit ... *)
  m_list_in_any_order ~less_is_ok:true m_type_ xsa xsb

(* ------------------------------------------------------------------------- *)
(* Class definition *)
(* ------------------------------------------------------------------------- *)
(* TODO: there are a few remaining m_list m_type_ we could transform
 * to use instead m_list__m_type_, for Exception, TyTuple and OrConstructor
 * but maybe quite different from list of types in inheritance
 *)

(*s: function [[Generic_vs_generic.m_class_definition]] *)
and m_class_definition a b =
  match (a, b) with
  | ( {
        A.ckind = a1;
        cextends = a2;
        cimplements = a3;
        cmixins = a5;
        cbody = a4;
        cparams = a6;
      },
      {
        B.ckind = b1;
        cextends = b2;
        cimplements = b3;
        cmixins = b5;
        cbody = b4;
        cparams = b6;
      } ) ->
      m_class_kind a1 b1 >>= fun () ->
      (* TODO: use also m_list_in_any_order? regressions for python? *)
      m_list__m_type_ a2 b2 >>= fun () ->
      m_list__m_type_any_order a3 b3 >>= fun () ->
      m_list__m_type_any_order a5 b5 >>= fun () ->
      m_parameters a6 b6 >>= fun () -> m_bracket m_fields a4 b4

(*e: function [[Generic_vs_generic.m_class_definition]] *)

(*s: function [[Generic_vs_generic.m_class_kind]] *)
and m_class_kind a b = m_wrap m_class_kind_bis a b

and m_class_kind_bis a b =
  match (a, b) with
  | A.Class, B.Class
  | A.Interface, B.Interface
  | A.Trait, B.Trait
  | A.AtInterface, B.AtInterface
  | A.Object, B.Object
  | A.RecordClass, B.RecordClass ->
      return ()
  | A.Class, _
  | A.Interface, _
  | A.Trait, _
  | A.AtInterface, _
  | A.Object, _
  | A.RecordClass, _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_class_kind]] *)

(* ------------------------------------------------------------------------- *)
(* Module definition *)
(* ------------------------------------------------------------------------- *)

(*s: function [[Generic_vs_generic.m_module_definition]] *)
and m_module_definition a b =
  match (a, b) with
  | { A.mbody = a1 }, { B.mbody = b1 } -> m_module_definition_kind a1 b1

(*e: function [[Generic_vs_generic.m_module_definition]] *)

(*s: function [[Generic_vs_generic.m_module_definition_kind]] *)
and m_module_definition_kind a b =
  match (a, b) with
  | A.ModuleAlias a1, B.ModuleAlias b1 -> m_dotted_name a1 b1
  | A.ModuleStruct (a1, a2), B.ModuleStruct (b1, b2) ->
      (m_option m_dotted_name) a1 b1 >>= fun () -> (m_list m_item) a2 b2
  | A.OtherModule (a1, a2), B.OtherModule (b1, b2) ->
      m_other_module_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.ModuleAlias _, _ | A.ModuleStruct _, _ | A.OtherModule _, _ -> fail ()

(*e: function [[Generic_vs_generic.m_module_definition_kind]] *)

(*s: function [[Generic_vs_generic.m_other_module_operator]] *)
and m_other_module_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_module_operator]] *)

(* ------------------------------------------------------------------------- *)
(* Macro definition *)
(* ------------------------------------------------------------------------- *)

(*s: function [[Generic_vs_generic.m_macro_definition]] *)
and m_macro_definition a b =
  match (a, b) with
  | ( { A.macroparams = a1; macrobody = a2 },
      { B.macroparams = b1; macrobody = b2 } ) ->
      (m_list m_ident) a1 b1 >>= fun () -> (m_list m_any) a2 b2

(*e: function [[Generic_vs_generic.m_macro_definition]] *)

(*****************************************************************************)
(* Directives (Module import/export, macros) *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_directive]] *)
and m_directive a b =
  m_directive_basic a b >!> fun () ->
  match a with
  (* normalize only if very simple import pattern (no alias) *)
  | A.ImportFrom (_, _, _, None) | A.ImportAs (_, _, None) -> (
      (* equivalence: *)
      let normal_a = Normalize_generic.normalize_import_opt true a in
      let normal_b = Normalize_generic.normalize_import_opt false b in
      match (normal_a, normal_b) with
      | Some (a0, a1), Some (b0, b1) ->
          m_tok a0 b0 >>= fun () -> m_module_name_prefix a1 b1
      | _ -> fail () )
  (* more complex pattern should not be normalized *)
  | A.ImportFrom _ | A.ImportAs _
  (* definitely do not normalize the pattern for ImportAll *)
  | A.ImportAll _ | A.Package _ | A.PackageEnd _ | A.Pragma _
  | A.OtherDirective _ ->
      fail ()

(*e: function [[Generic_vs_generic.m_directive]] *)

(* less-is-ok: a few of these below with the use of m_module_name_prefix and
 * m_option_none_can_match_some.
 * todo? not sure it makes sense to always allow m_module_name_prefix below
 *)
(*s: function [[Generic_vs_generic.m_directive_basic]] *)
and m_directive_basic a b =
  match (a, b) with
  (*s: [[Generic_vs_generic.m_directive_basic]] import cases *)
  (* metavar: import $LIB should bind $LIB to the full qualified name *)
  | ( A.ImportFrom (a0, DottedName [], (str, tok), a3),
      B.ImportFrom (b0, DottedName xs, x, b3) )
    when MV.is_metavar_name str ->
      let name = H.name_of_ids (xs @ [ x ]) in
      let* () = m_tok a0 b0 in
      let* () = envf (str, tok) (MV.N name) in
      (m_option_none_can_match_some m_ident_and_id_info) a3 b3
  | A.ImportFrom (a0, a1, a2, a3), B.ImportFrom (b0, b1, b2, b3) ->
      m_tok a0 b0 >>= fun () ->
      m_module_name_prefix a1 b1 >>= fun () ->
      m_ident_and_empty_id_info a2 b2 >>= fun () ->
      (m_option_none_can_match_some m_ident_and_id_info) a3 b3
  | A.ImportAs (a0, a1, a2), B.ImportAs (b0, b1, b2) ->
      m_tok a0 b0 >>= fun () ->
      m_module_name_prefix a1 b1 >>= fun () ->
      (m_option_none_can_match_some m_ident_and_id_info) a2 b2
  | A.ImportAll (a0, a1, a2), B.ImportAll (b0, b1, b2) ->
      m_tok a0 b0 >>= fun () ->
      m_module_name_prefix a1 b1 >>= fun () -> m_tok a2 b2
  (*e: [[Generic_vs_generic.m_directive_basic]] import cases *)
  (* boilerplate *)
  (*s: [[Generic_vs_generic.m_directive_basic]] boilerplate cases *)
  | A.Package (a0, a1), B.Package (b0, b1) ->
      m_tok a0 b0 >>= fun () -> m_dotted_name a1 b1
  | A.PackageEnd a1, B.PackageEnd b1 -> m_tok a1 b1
  | A.Pragma (a1, a2), B.Pragma (b1, b2) ->
      m_ident a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.OtherDirective (a1, a2), B.OtherDirective (b1, b2) ->
      m_other_directive_operator a1 b1 >>= fun () -> (m_list m_any) a2 b2
  | A.ImportFrom _, _
  | A.ImportAs _, _
  | A.OtherDirective _, _
  | A.Pragma _, _
  | A.ImportAll _, _
  | A.Package _, _
  | A.PackageEnd _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_directive_basic]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_directive_basic]] *)

(*s: function [[Generic_vs_generic.m_other_directive_operator]] *)
and m_other_directive_operator = m_other_xxx

(*e: function [[Generic_vs_generic.m_other_directive_operator]] *)

(*****************************************************************************)
(* Toplevel *)
(*****************************************************************************)

(*s: function [[Generic_vs_generic.m_item]] *)
and m_item a b = m_stmt a b

(*e: function [[Generic_vs_generic.m_item]] *)

(*s: function [[Generic_vs_generic.m_program]] *)
and m_program a b = match (a, b) with a, b -> (m_list m_item) a b

(*e: function [[Generic_vs_generic.m_program]] *)

(*****************************************************************************)
(* Any *)
(*****************************************************************************)
and m_partial a b =
  match (a, b) with
  | A.PartialDef a1, B.PartialDef b1 -> m_definition a1 b1
  | A.PartialIf (a1, a2), B.PartialIf (b1, b2) ->
      let* () = m_tok a1 b1 in
      m_expr a2 b2
  | A.PartialTry (a1, a2), B.PartialTry (b1, b2) ->
      let* () = m_tok a1 b1 in
      m_stmt a2 b2
  | A.PartialFinally (a1, a2), B.PartialFinally (b1, b2) ->
      let* () = m_tok a1 b1 in
      m_stmt a2 b2
  | A.PartialCatch a1, B.PartialCatch b1 -> m_catch a1 b1
  | A.PartialSingleField (a1, a2, a3), B.PartialSingleField (b1, b2, b3) ->
      let* () = m_ident a1 b1 in
      let* () = m_tok a2 b2 in
      m_expr a3 b3
  | A.PartialLambdaOrFuncDef a1, B.PartialLambdaOrFuncDef b1 ->
      m_function_definition a1 b1
  | A.PartialDef _, _
  | A.PartialIf _, _
  | A.PartialTry _, _
  | A.PartialCatch _, _
  | A.PartialFinally _, _
  | A.PartialSingleField _, _
  | A.PartialLambdaOrFuncDef _, _ ->
      fail ()

(*s: function [[Generic_vs_generic.m_any]] *)
and m_any a b =
  match (a, b) with
  | A.Str a1, B.Str b1 -> m_string_ellipsis_or_metavar_or_default a1 b1
  | A.Ss a1, B.Ss b1 -> m_stmts_deep ~less_is_ok:true a1 b1
  | A.E a1, B.E b1 -> m_expr a1 b1
  | A.S a1, B.S b1 -> m_stmt a1 b1
  (*s: [[Generic_vs_generic.m_any]] boilerplate cases *)
  | A.Partial a1, B.Partial b1 -> m_partial a1 b1
  | A.Args a1, B.Args b1 -> m_list m_argument a1 b1
  (* boilerplate *)
  | A.Modn a1, B.Modn b1 -> m_module_name a1 b1
  | A.ModDk a1, B.ModDk b1 -> m_module_definition_kind a1 b1
  | A.Tk a1, B.Tk b1 -> m_tok a1 b1
  | A.TodoK a1, B.TodoK b1 -> m_ident a1 b1
  | A.Di a1, B.Di b1 -> m_dotted_name a1 b1
  | A.En a1, B.En b1 -> m_entity a1 b1
  | A.T a1, B.T b1 -> m_type_ a1 b1
  | A.P a1, B.P b1 -> m_pattern a1 b1
  | A.Def a1, B.Def b1 -> m_definition a1 b1
  | A.Dir a1, B.Dir b1 -> m_directive a1 b1
  | A.Fld a1, B.Fld b1 -> m_field a1 b1
  | A.Pa a1, B.Pa b1 -> m_parameter a1 b1
  | A.Ar a1, B.Ar b1 -> m_argument a1 b1
  | A.At a1, B.At b1 -> m_attribute a1 b1
  | A.Dk a1, B.Dk b1 -> m_definition_kind a1 b1
  | A.Pr a1, B.Pr b1 -> m_program a1 b1
  | A.I a1, B.I b1 -> m_ident a1 b1
  | A.Lbli a1, B.Lbli b1 -> m_label_ident a1 b1
  | A.NoD a1, B.NoD b1 -> m_name_or_dynamic a1 b1
  | A.I _, _
  | A.Modn _, _
  | A.Di _, _
  | A.En _, _
  | A.E _, _
  | A.S _, _
  | A.T _, _
  | A.P _, _
  | A.Def _, _
  | A.Dir _, _
  | A.Pa _, _
  | A.Ar _, _
  | A.At _, _
  | A.Dk _, _
  | A.Pr _, _
  | A.Fld _, _
  | A.Ss _, _
  | A.Tk _, _
  | A.Lbli _, _
  | A.NoD _, _
  | A.ModDk _, _
  | A.TodoK _, _
  | A.Partial _, _
  | A.Args _, _
  | A.Str _, _ ->
      fail ()

(*e: [[Generic_vs_generic.m_any]] boilerplate cases *)
(*e: function [[Generic_vs_generic.m_any]] *)
(*e: semgrep/matching/Generic_vs_generic.ml *)
